A study of the initialization stage for evolutionary algorithms with limited computational resources : application, resource allocation, and classification

Abstract

This work studies the initialization procedure of Evolutionary Algorithms (EAs) under computational expensive environment.

EAs mimics the natural evolution process in which solutions evolve from generation to generation, yielding better solutions in the process. In each generation, all solutions will be evaluated and new solutions will be created by mating existing solutions, followed by a selection, to form the next generation. The first generation, also known as initial solutions, need to be generated by other approaches, also known as Initialization Techniques. EAs is population-based algorithm and its performance is affected by initial solution. The literature has been focused more on inventing new methods to generate initial solutions while rarely studying how different initial solutions can change optimization performances.

In this work, we focus on the computational expensive environment where the computational resources are severely limited. Such limited resource greatly restricts the number of available solution evaluations, rendering initial solutions a higher importance than normal situations. During the whole EAs process, generating initial solutions is referred to as the Initialization Stage and running EAs operators is referred to as the Optimization Stage. We start with verifying the influence from better initial solutions by solving the Unit Commitment (UC) problem. Then to understand how EAs performances is related to the initialization stage under computational expensive environment, we hypothesize that the Resource Allocation Ratio (RA) between two stages is a key factor. To verify our hypothesis and demonstrate the importance of RA, we first modify the framework of general EAs workflow so that RA can be controlled separately while keeping all other factors constant. Based on the new framework, we conduct extensive simulations and show that RA has a significant effect in changing EAs performances. This effect persists regardless of how initial solutions are generated. By testing EAs performances given different RA values and other EAs factors, we further show that there exists optimal RAs that optimize EAs performances.

After showing the existence of the importance of RA and the factors on which it depends, we build a framework to efficiently find the optimal RA on new problems. Based on our simulation results, problems can be categorized by their optimal RA. Optimal RA for each category is unique. To classify new problems into known categories, sampling and information content techniques are applied to characterize the features of optimization problems. Then a classification model is trained and validated with problem features as input and problem categorizations as output. Results on test problems prove the effectiveness of our classification model. With this classification model, we are able to use a small fraction of computational resources to figure out the optimal RA for a new problem and apply it to enhance optimization performance.

Major contributions of this work are concluded as follows: • proposing RA as a new EAs factor and demonstrating its importance in deciding EAs performances; • analyzing factors that affect the optimal RA and finding its general values for different problem categories; • developing a general framework to predict the optimal RA for new problems.