Abstract:

Interactive genetic algorithms, whose individual’s fitness is assigned by a user, are effective methods to solve a complicated optimization problem with its indices being hard or even impossible to be explicitly described. In order to alleviate user fatigue and improve the algorithm’s performance, we presented an efficient interactive genetic algorithm with extracting evolutionary knowledge based on a directed graph. First, some pairs of tournament evaluated evolutionary individuals were constructed according to the evolutionary population, and the dominance relations of these individuals were obtained. Then a directed graph was built, an individual’s fitness was calculated by using the indegree and outdegree of its corresponding vertex of the directed graph, and some superior individuals as well as building blocks were obtained. Finally, some new individuals were generated based on these building blocks and involved in the subsequent evolutions. The proposed algorithm was applied in a fashion evolutionary design system and the results showed the algorithm’s advantage in alleviating user fatigue and improving search performance.

Key words: optimization, genetic algorithms, interaction, directed graph, building block