Category: Uncategorized

We present a genetic programming (GP) system to evolve reusable heuristics for the 2-D strip packing problem. The evolved heuristics are constructive, and decide both which piece to pack next and where to place that piece, given the current partial solution. This paper contributes to a growing research area that represents a paradigm shift in search methodologies. Instead of using evolutionary computation to search a space of solutions, we employ it to search a space of heuristics for the problem. A key motivation is to investigate methods to automate the heuristic design process. It has been stated in the literature that humans are very good at identifying good building blocks for solution methods. However, the task of intelligently searching through all of the potential combinations of these components is better suited to a computer. With such tools at their disposal, heuristic designers are then free to commit more of their time to the creative process of determining good components, while the computer takes on some of the design process by intelligently combining these components. This paper shows that a GP hyper-heuristic can be employed to automatically generate human competitive heuristics in a very-well studied problem domain.

In the design of evolutionary multiobjective optimization (EMO) algorithms, it is important to strike a balance between diversity and convergence. Traditional mask-based crossover operators for binary strings (e.g., one-point, two-point, and uniform) tend to decrease the spread of solutions along the Pareto front in EMO algorithms while they improve the convergence to part of the Pareto front. This is because such a crossover operator, which is called geometric crossover, always generates an offspring in the segment between its two parents under the Hamming distance in the genotype space. That is, the sum of the distances from the generated offspring to its two parents is always equal to the distance between the two parents. In this paper, we first propose a non-geometric binary crossover operator to generate an offspring outside the segment between its two parents. Next, we show some properties of our crossover operator. Then we examine its effects on the behavior of EMO algorithms through computational experiments on knapsack problems with two, four, and six objectives. Experimental results show that our crossover operator can increase the spread of solutions along the Pareto front in EMO algorithms without severely degrading their convergence property. As a result, our crossover operator improves some overall performance measures such as the hypervolume.