kri5t0fk / souvlakisearch Goto Github PK

For unvisitedVertices I'd suggest using PriorityQueue<TElement, TPriority> instead of looking for nearest vertex manually.

PriorityQueue<indexT, edgeWeightT(minCostToVertex)> unvisitedVertices = new PriorityQueue<indexT, edgeWeightT(minCostToVertex)>();

Originally posted by @Kri5t0fK in #21 (comment)

On pushes, PRs:

• Automatic Build,
• Automatic Testing

We need to have public access for this class for purpose of unit tests. If this class is not supposed to be tested, then you can leave it as is and close this issue.

Suggestion:

1. Produce two random integers $i,j \in [1,n]$,
2. then exchange the values of $v_i$ and $v_j$ to make new partnership scheme.

Example:

input: $[ABCDEF]$ (vector of vertices),
$i, j = 2, 5$,
$[AB\fbox{C}DE\fbox{F}]$ - before swap,
$[AB\fbox{F}DE\fbox{C}]$ - after swap,
return $[ABFDEC]$,

Steps

1. Randomly select pairs of Parents
2. For each pair -> run crossover (suggestion below)
3. give output to Mutation (#12) or straight to Selection (#15)

Useful materials:

• PMX Crossover Operator (step by step)
• [Wikipedia] GA Crossover - for permutations
• Wykład - Algorytmy Genetyczne (p. 72-76)

Suggestion - PMX (partialy-mapped crossover):

1. input: parents:
   P1: $[\underline{ABCDEFGH}]$ (underline for genes from parent 1)
   P2: $[HEFGDABC]$
2. Random crossover segment (should, but don't have to be next to each other)
   P1: $[\underline{ABC}\boxed{\underline{DEF}}\underline{GH}]$
   P2: $[HEF\boxed{GDA}BC]$
3. Start Childs (leave picked vertices P1->C1, P2->C2):
   C1: $[\square\square\square|\underline{DEF}|\square\square]$
   C2: $[\square\square\square|GDA|\square\square]$
4. Copy non-conflicting genes to Child from other Parent (P1->C2, P2->C1):
   C1: $[H\square\square|\underline{DEF}|BC]$ - $E, F$ can't be copied from P2, because are in $\{DEF\}$
   C2: $[\square\underline{BC}|GDA|\square\underline{H}]$ - $A, G$ can't be copied from P2, because are in $\{GDA\}$
5. Fill remaining genes in Child - based on exchange-pairs from [2.] crossover segment:
   Do the change recursively, until you get vertex that wasn't in child yet.
   For C1: DEF->GDA => D->G, E->D, F->A
   For C2: GDA->DEF => G->D, D->E, A->F
   - Trying just putting (like in 4.) -> collision -> vertices in boxes need changing:
   C1: $[H\boxed{EF}|\underline{DEF}|BC]$ - E: E->D->G; F: F->A
   C2: $[\boxed{A}\underline{BC}|GDA|\boxed{G}\underline{H}]$ - A: A->F; G: G->D->E
   - After change:
   C1: $[H\hat{G}\hat{A}|\underline{DEF}|BC]$
   C2: $[\hat{F}\underline{BC}|GDA|\hat{E}\underline{H}]$
6. Return childs:
   C1: $[HGADEFBC]$
   C2: $[FBCGDAEH]$

Maybe also add get() for entire List _oddVertices?

Run it parallelly when used to calculate odd pairs's distances.

• used inside of #9

• Find applied solutions (if exist).
• Prepare a comparison of methods.
• Prepare bibliography.
• Add to README

Basic idea

Based on Fitness score (#14) -> select individuals that will give offspring (crossover #13).
Also, after new offspring is produced -> kill weak individuals (low fitness score), so new Population (Generation #17) is stronger.

• Parents can stay alive, and crossover with children.

Rename fields of Map class to better suit mathematical conventions. For example change:

• Map to Graph
• Intersections to Vertices
• Roads to Edges
  Refers to both Map.cs and Dijkstra.cs

Main GA (Genetic Algorithm) Issue - other link to that one.

Subtasks:

• #16
• #17
• #11
• #14
• #23
• #15
• #12
• #13

Algorithm Steps (approximately):

1. Initialization #11
2. Loop
   1. Calculate Fitness/Cost for entire population (#14)
   2. Stop/Termination condition (#23)
   3. Select solutions from population for crossover (roulette/elite) (#15)
   4. Crossover (with probability, not all individuals) (#13)
   5. Mutation (with not high probability (#12)

Useful materials:

• [AGH] Algorytmy genetyczne
• [Wikipedia] Genetic algorithm

A population is a set/list/vector of individuals (solutions/genotypes #16)
It should have constant size (kept to not get bigger by Selection #15)

Currently genotype stores a list of vertices. This isn't necessarily a bad way to store data, but it is far from being space efficient - every Vertex contains both Vector2 holding position on screen and a full list of Edge objects. Therefore I'd suggest, that Genotype stores a list of indices instead, and gets all Vertex info from the reference to the original Graf object.

PLEASE make those changes on GA-algorithm-dev branch, cause I dont want to jump over three different branches, just to check for potential merges every time I open Visual Studio

Useful materials:

• [Wikipedia] Genetic Algorithm#Termination

Suggestions:

• Minimum criteria satisfied
• Fixed number of generations reached
• Successive iterations no longer produce better results
• Combinations of the above

Base

Genotype consists of 2n (even number) of Odd Vertexes (road crossings): $\{A, B, C, D, E, F\}$

List of elements (permutations)

• Genotype of one individual (candidate solution) is just a list of vertexes in any order:
  $X=[A B C D E F]$
• each vertex only once
• Pairs - consecutive: $pair(X_{2i}, X_{2i+1}), i={0,1,2,..}$
  soo... virtual split: $X=[A B | C D | E F] \implies$ pairs: $\{AB, CD, EF\}$

Easiest method - random:

• Gets:
  • list of odd vertices: $[ABCDEF]$
  • size of Population
• Returns: Population(#17): list/set of Solutions
  • generation of 1 Solution: odd vertices in random order

Example:

Input: odd vertices= $[ABCDEF]$, pop_size=4,
Return: $\{[FBACDE], [CDABFE], [EABCFD], [BFCEDA]\}$

Fitness/Cost function:

Calculate Dijkstra (#6) for every pair in solution-vector and sum all costs:
$\text{CostFunction}([AB|CD|EF]) = \text{Dijkstra}(AB).cost+\text{Dijkstra}(CD).cost+\text{Dijkstra}(EF).cost$