report.tex

Case for the Swap mutation

    Since the atsp is mostly about recombination and a chromosome already
    contains all possible genes. The swap tactic is as effective
    as any other intricate way of mutation.

    This is attributed to the fact that the procedures that guarantee the
    no-duplicate policy (do not visit the same city twice), often take more
    time (just like set addition in python).

    So the Swap mutation is appropriate for the problems of recombinatory sort,
    where a chromosome contains all possible genes and so every gene has to
    occur only once.

    Another way of approaching the uniqueness of set, is via selection tactic:
    penalty the chromosomes that repeat a gene, render them useless. But in this
    scenario, the search for allele-unique chromosomes is a problem in itself
    that will take more of the unnecessary processing power.


Crossover

    PMX crossover between parents seems to be the most fitting tactic amongst
    the operators mentioned in the textbook. However, I do not implement this
    crossover operator for this problem: instead, I go for a simpler solution
    of splicing children by some index, depending on the dominance of each
    parent.

    n-th from first parent and to the position where the second parent has m.
    m-th from the second parent to the position where the first parent has n.


Mutation rate and mating rate



This report describes my findings in an attempt to solve an
asymmetric travelling salesman problem through the approach
of genetic algorithm.

The solution utilizes fitness score as integer for increased precision
and speed. For certain application the fitness can be converted to
ratios of fitness represendet as floating point numbers via rank-function
that returns a sorted list of individuals


Set up a list of possible constraints this exercise falls under:

    _Problem specific:
    Encoding (yes/no)? If yes, which one?
    Uniqueness of a gene in a chromosome
    Uniqueness of a chromosome in the pool
    Length of a chromosome (fixed or variable)
    Size of the population (fixed or variable)
    Evaluation strategy: ranking, normalization, distribution
    The representation of fitness: minimalization or maximalization problem?
    Termination conditions
    Ordering is important: which crossover needs does this lead to?


    _Algorithm specific:
    Parent selection
    Survivor selection


It might be a good practice to encode all the data at once, and decode only
when visual feedback is needed.

Do a progress evaluation: a period of no progress
(in comparison to the previous): STOP