Ranking Techniques in Multicriteria Genetic Algorithm-Based Optimization


Abstract

The purpose of this research was to develop new ranking techniques for multi-criteria genetic algorithms by testing them in a complex problem domain and comparing them to conventional methods. Multi-criteria genetic algorithm-based optimization requires an intermediate process referred to as ranking. Multi-criteria problems have multiple objectives that store their results in arrays. Genetic algorithms process input vectors and are not able to handle the multi-criteria result arrays. Ranking methods are used to convert arrays into vectors and feed the vectors to the genetic algorithm. An efficient ranking technique will accomplish two tasks: a) convert an array into a vector and b) transfer the array's dimensionality to the vector. Three stand-alone ranking methods and two ranking enhancements were tested. The ranking methods were conventional summation, Pareto optimality and Variant Ordered Weighted Averaging (VOWA). Summation ignored dimensionality, Pareto and VOWA included dimensionality. The enhancements were the conventional hill climbing search strategy and the Membership Inferencing Factor (MIF) for dimensionality translation. VOWA and MIF were new methods and this research focused on their performance relative to the conventional methods: summation and Pareto. The experimental framework in this research was designed to test each ranking method on a near impossible, real world multi-criteria optimization problem. The problem was broken into four levels of complexity (i.e., the complexity of a level was based on the number of objective functions that were being optimized at that level). Each ranking method (enhanced and un-enhanced) was used in conjunction with the genetic algorithm-based optimization at all four complexity levels. The performance of each ranking method was recorded acorss the various levels. Of the three stand-alone ranking methods tested (summation,Pareto, or VOWA), none of them consistently produced the best solutions across all complexities. But a hybrid ranking method (combined MIF-hill climbing VOWA) did statistically out-perform all the other methods tested and consistently found the best solutions at every level of complexity. This hybrid ranking method did not exist before this investigation and it was the first time that this combination of techniques was applied to ranking and multi-criteria optimization.