Genetic Algorithm Essentials

1. Traveling Salesman problem
2. OneMax

1. difficulty
   1. unsteadiness
   2. noise
   3. to many local optima
2. found
   1. local
      1. 4 - Multimodality
         1. avoid getting stuck
         2. Restarts
            1. different starting conditions
            2. chance high to reach new local optima
         3. Global mutation rates
         4. Fitness sharing

            Annotations:

            • • neighboring or the ones that belong to one cluster • clustering techniques like k-means or DBSCAN • evolutions within shared region is random walk
            1. hilly fitness landscape
         5. Novelty search
            1. avoid known solutions
            2. bias search towards unknown solution areas
            3. use outlier detection methods
         6. Niching
            1. clustering techniques
               1. k-means
               2. DBSCAN

                  Annotations:

                  • • define core points with density of solutions • if more than minPts solutions in epsilon radius, point is core point • core points that have core points in their neighborhood belong to one cluster • points that are within radius of core points but are not core points are corner points • rest is noise
               3. hierarchical clustering
            2. run separate GA
            3. Tree Niching
               1. Follow the worse solution for g generations
               2. After g generations follow better branch
   2. global

1. 1-Point crossover
2. Arithmetic crossover
3. Dominant crossover

1. properties
   1. Reachability

      Annotations:

      •  each point in solution space must be reachable from an arbitrary point in solution space .  
   2. Unbiasedness

      Annotations:

      •  The mutation operator should not induce a drift of the search to a particular direction. 
   3. Scalability

      Annotations:

      •  The mutation rate should be adjustable.  
2. examples
   1. Bit flip
   2. Random resetting
   3. Gaussian mutation

      Annotations:

      •  x_ = x + sigma * np.random.standard_normal(10)  
      1. x' = x + σ · N (0, 1)
3. mutation rate sigma
   1. Selft-adaptation
      1. sigma' = simgma' * exp(tau * N(0,1))
      2. each chromosome gets an own σ
   2. Mutation Rate Controls
      1. Dynamic Control
         1. adapt parameter depending on
            1. time
            2. generation counter
         2. changes parameter during run
      2. Rechenberg
         1. success (>1/5) -> σ' = σ · τ
         2. no success (<1/5) -> σ' = σ / τ
         3. rate -> 1/5 = keep σ constant
      3. Constant mutation rate

Annotations:

• • map chromosome to solution to evaluate fitness • example: map bit string to pipeline of machine learning commands in sklearn  

1. effiiciency
   1. find optimum
   2. approximation in fitness evaluations
2. 6 - Multiple Objectives
   1. two or more objectives at a time
   2. Pareto
      1. op. sol. in single-objective optimization corresponds to Pareto-set in multi-objective optimization
      2. not dominated solutions are Pareto-optimal
      3. Pareto-set
      4. formal
         1. f = w · f 1 + (1 - w) · f 2
         2. w \in (0, 1)
      5. Non-dominated sorting
         1. non-dominated = rank 1
         2. if remove rank i, remaining non-dominated solutions get rank i+1
      6. NSGA-II
         1. selection solutions with maximal crowding distance
         2. seeks for a broad coverage
         3. sum of differences between fitness of left and right
      7. Rake
         1. affords evolution of corner points
         2. rake selection selects the ones that minimize the distance to closest rake
         3. rake base between leftest and rightest solution
      8. Hypervolume
         1. greedy heuristic: (μ + 1)-GA that discards solution with least hypervolume contribution
         2. reference point = badly dominated solution
         3. exhaustive for n > 3
         4. each solution dominates area (n = 2) or volume (n > 2)
         5. S-metric selection
   3. conflicting: price and performance
   4. multiple fitness functions
   5. no single optimal solution

Annotations:

• •  To allow convergence towards optimal solutions, the best offspring solutions have to be selected to be parents for the new parental population. • Surplus of offspring is generated, best parents are selected to allow approximation  

1. Elitist selection
   1. plus selection
   2. comma selection
2. Forgetting
   1. Roulette wheel selection
   2. Tournament
   3. to overcome

1. after # fitnessfunctions
2. after # generations
3. after stagnation

1. measure means
2. standard deviiantion
3. Best and worste fitness

1. Meta-GA
   1. inefficient, but effective
   2. GA tunes GA
   3. MGA starts GA to optimize the GA Parameters like tau
2. tuning

1. Penalty functions

   Annotations:

   • penalty functions deteriorate fitness for infeasible solutions
   1. walk into infeasible
   2. deteriorate fitness

      Annotations:

      • verschlechtern
   3. f'(x) = f(x) + alpha * G(x)
   4. fitness function evaluations are not always possible
   5. Penalty adaptation
      1. at the end
      2. depending on
         1. generation number
         2. number of infeasible solutions
         3. increase/decrease at border of feasibility
2. Solution space
3. formal
   1. g(x) < 0 is constraint function
   2. G(x) = max (0, g(x))
   3. f(x) is fitness function
4. Death penalty
   1. in such cases does not terminate
   2. may suffer from premature stagnation
5. Repair function
   1. depending on representation and problem structure
   2. examples
      1. linear projection in continuous solution spaces
      2. TSP problem: repair tour
   3. for consistence of GA search
6. Decoders
   1. map constrained solution space to
      1. an unconstrained one
      2. solution space with less difficult conditions
   2. mapping must capture characteristics of solution space
   3. neighboring solutions in original space must be neighboring in decoder space
7. Premature Stagnation
   1. How to prevent?
      1. adaptation of mutation ellipsoid to increase success probabilities
      2. minimum mutation rate, but this also prevents convergence
   2. at boundary of infeasible solution space success probabilities are often low
   3. good solutions can be further away from unconstrained optimum

1. there is no overall superior optimization algorithm that is able to solve all kinds of optimization problems
2. algorithm that performs well on one problem, will probably fail on many other problems
3. Good News
   1. it is possible to design algorithms working well on broad problem class

1. Laufzeitanalyse für (1+1)-GA
   1. O(N log N)
   2. k/N * (1 - 1/N)^(N - 1)
      1. flip k 0 bits
      2. do not flip N-1 bits
   3. proof
2. fitness-based partitions

1. treat populations in each generations as states
2. modelled with matrix of transition probabilities
3. independent of current state from predecessor
4. convergence to global optimum with elitism
5. a GA optimizing a function over an arbitrary finite space converges to optimum with probability one

1. local convergence measures evaluating amelioration power of GAs
2. population-based GA with plus selection always performs better than with comma selection

1. proportion of individuals representing schema at subsequent time-steps is product of probabilities of being selected and not being disrupted

1. while schema theorem only considers disruptive effects, BBH considers constructive effects
2. O(N 2 log N) with crossover
3. O(N^k) without Crossover

1. lets the mutation operator adapt to solution space characteristics
2. covariance matrix estimated during an optimization run of a GA on Sphere function

1. use f to predict fitness of x
2. comprise solution x and fitness f(x) pair as pattern- label pair
3. exploration strategy: try new solutions for optimization or for improvement of meta-model

1. learning with labels
2. training set T = {(x 1 ,y 1 ), (x 2 ,y 2 ), ..., (x N ,y N )}
3. classification
   1. y = 0 or 1, feasible or infeasible
4. regression
   1. y is numerical (e.g. 0.634, 12.39, fitness values)

1. same works for constraints
2. comprise constraint satisfaction prediction as classification problem

1. Dimensionality reduction for visualization
   1. mapping of high-dimensional population to low dimensional space
2. map high-dimensional patterns to abstract low- dimensional spaces
3. principal component analysis
   1. PCA detects axes in the data that employ highest variances
   2. projections of patterns onto these axes