4. Nonlinear optimization with Genetic Algorithms #

4.0.1 Collaboration #

If you want, you may team up with a fellow student. In this case, both code and report may be written together. Both students are fully responsible of the project, and must be able to demonstrate understanding of each others code and results.

4.0.2 Presentation #

You are given time for a small, max. 5-minute, presentation at the end of the course. This is mostly an opportunity to share what you have been working on.

• A single or a few slides suffice!
• Keep it to 5 minutes.
• Highlight a result that you obtained, an interesting part of your work, or explain some interesting code, or optimization/GA algorithm.
• For collaborations: both give an individual (possibly connected) 5-minute presentation.

4.1 Writing a Genetic Algorithms library #

Download and extract the Genetic Algorithms (GA) Library archive file. The ZIP includes:

• The headstart of a Genetic Algorithms library.
• The start of an integer maximization problem.

Read CourseBook 4.1, and study the code for the IntegerMaximizationProblem. This is a test problem, where the goal is to optimize over nonnegative integers. The integer solutions are encoded in IntegerChromosome objects, which internally hold a bitstring std::list of length $n$. The GeneticAlgorithm should, through selection, mutation and crossover, find an IntegerChromosome with an all-ones bitstring, corresponding to the value $2^n -1$.

• Implement the marked functions in IntegerChromosome and its base class. [CourseBook exercise 4.2]
• Implement mutation_(). [CourseBook exercise 4.4]
• Implement reproduce_(). [CourseBook exercise 4.5]

Run a few testcases the effect of different parameters, such as crossover probability, mutation probability and population size. For $n=8$ and a population of a couple of hundred members, the optimum is usually found in a few hundred generations.

Writing This exercise, 4.1, is just to get you started with Genetic Algorithms, and is not needed in your report.

4.1.1 Elitism #

With elitism (CourseBook section 4.3.1), a limited number of chromosomes members always survive to a successive generation, and are invulnerable to mutations. This prevents accidentally destroying the better members of the chromosome population.

The following list gives a few suggestions to implementing elitism. You can pick a strategy that suits you best, or think of an own strategy.

• One approach would track the elite members in a dedicated vector in GeneticAlgorithm. In reproduce_() and mutate_() the vector needs to be consulted.
• A different approach is to make a Chromosome base class, and have a Chromosome::elite() getter and setter.
• Yet another approach looks for the $n$-th highest objective value, and considers all members above this objective value elite.

4.2 TSP or project of choice #

After having your code up and running, you are free to propose a final project. In the CourseBook there are a few suggested topics: the Traveling Salesman Problem (TSP) and Charges on a sphere. As an alternative, you may look for an optimization problem that has affinity with Genetic Algorithms. There are many such: Machine Learning, games and puzzles, scheduling, physics, and so on.

4.2.1 Traveling Salesman Problem (CourseBook 4.4.1) #

The following code should get you started on the TSP problem with Genetic Algorithms, using example problems from TSPLIB.

A few suggestions for your project:

• Implement different crossover and mutation algorithms for TSP (greedy crossover, ordered crossover, etc.). A few ideas and references are given in this paper.
• Implement a local search strategy for TSP, such as are given in the CourseBook.
• Try to find an optimal solution to the 29-city bays29 problem (in as little iterations as possible).
• Try to find an optimal solution to a larger TSPLIB problem (more than 70 cities).
• Research a variant of the TSP problem (a few are given on the TSPLIB webpage).
• Have a look at more involved GA concepts for fitness and selection.

Tips:

• It is interesting to look at a few parameter ranges, but try to avoid an extensive high-level parameter study.
• Modify and expand the given code to fit the needs of your project. Use your knowledge about object-oriented techniques and C++ programming to keep the code organized and fast.