Micro-Genetic Algorithms(μGAs) for Hard Combinatorial Optimisation Problems

The current research to find near-optimum solution(s) explores in a small population, which is coined as Micro-Genetic Algorithms (μGAs), with some genetic operators. Just as in the Simple-Genetic Algorithms (SGAs), the μGAs work with encoding population and are implemented serially. The major difference between SGAs and μGAs is how to make reproductive plan for more better searching strategy due to the population choice. This paper is conducted to implement hybrid μGAs in order to achieve fast searching for more better evolution and associated cost evaluation in global solution space. To achieve this implementation, the Air-Borne Selection (ABS) for a new reproductive plan is developed as a new strategic conception for hybrid μGAs. It is shown that the general μGAs implementation reaches a near-optimal region much earlier than the SGAs implementation. The superior performance of the general μGAs is demonstrated with two kinds of hard combinatorial optimisation problems, which are Travelling Salesman Problem (TSP) and cutting path planning in nesting. And then, the superior performance of the hybrid μGAs is demonstrated for two types of nesting problems.