Nur Azmina Mohamad Zamani MSc Dissertation 2015/16

Experimental Performance Analysis for the Parameter-less Population Pyramid

Supervised by D.Sudholt

Abstract

There are many difficult optimisation  problems and evolutionary optimisation  techniques are often used to solve those problems. There are some evolutionary techniques that are parameter-less and some required parameter to perform the algorithm. For this project, we perform experiments with Parameter-less Population Pyramid (P3) to solve three combinatorial optimisation  problems which are 0-1 Knapsack, Makespan  Scheduling and MAX-SAT. P3 is a parameter-less evolutionary algorithm to perform optimisation  and forms a pyramid-like structure where each level has a population of solutions that represents the evolution. It is a combination of an efficient local search, Hill Climbing with model-building methods (clustering) of Linkage Learning Genetic Algorithm (LTGA) for crossover. Hence, P3 was p erformed  by building up a pyramid of expanding population iteratively where Hill Climbing was used to achieve local optimum and the clustering methods of performing the crossover was applied during the enhancement of the solutions (populations) in the pyramid.

Hill Climbing is performed by flipping each bit randomly (mutation) and evaluated to produce the local optimum (improving solution). Then, clustering is used to group decision variables to ensure the variables that belongs together (merged) remain together. This is called Cluster-creation in which P3 tries to learn what good building blocks are. The building blocks consist of good solutions which are useful during crossover. This merging is determined by calculating entropy and distance between the clusters. Finally, Cluster-usage is applied. In respect to the clusters obtained during Cluster-creation, the Cluster-usage and the donation process aim to combine good genetic information by performing crossover between the populations and the improving solution. The donation process will run over the populations randomly and the donor must be at least one gene different from the improving solution to be evaluated. Fitness improvement will be checked for evaluation to find the best solution. This method of clustering is an effective operator by storing the useful clusters and it is better than a standard crossover. This is because a standard crossover is usually quite disruptive and can destroy the good building blocks easily.

The experiment is performed by comparing P3 with Hill Climbing to observe the significance of the crossover method and also by comparing P3 with the modified P3 to observe the importance of applying the clustering technique. The modified P3 is where clustering method is removed. Therefore, we experiment with P3 using the variable sizes of 5, 10, 20, 50, 80 and 100 to measure the speed of the algorithms in obtaining its best fitness. Another analysis is performed to measure the average fitness over the number of generations for a fixed variable size. In addition, the number of evaluations varies during the generation and therefore, an analysis of average fitness over the number of evaluations is also conducted. These analyses are plotted using JFreeChart  JAVA library and the implementations are performed using JAVA with Eclipse as its platform. From the results obtained, P3 has been proven to have the best performance compared to Hill Climber and the modified P3. This is because P3 applies a hierarchical technique to achieve its best fitness in an efficient way.