A multi-population evolution stratagy and its application in low area/power FSM synthesis

Finding a low area/power state assignment is a NP-hard problem in finite-state machines synthesis. In order to solve this problem, this study proposes a multi-population evolution strategy, denoted as MPES. MPES accomplishes the task by using inner-ES and outer-ES. In inner-ES, subpopulations evolve separately and are responsible for local search in different regions. Alternating (μ + λ) strategy and (μ, λ) strategy are employed to select parental individuals from the ranked population for mutation. Three mutation operators, ‘replacement’, ‘2-exchange’ and ‘shifting’, perform on the parental individuals to generate offspring. Different fitness functions are defined for area and power evaluation, respectively. Outer-ES acts as a shell to optimize the subpopulations of inner-ES for better and better solutions. In outer-ES, the parameters of evolving subpopulations are represented by individuals of outer-population. Outer-ES performs selection and mutation on the outer-population to change the parameters of evolving subpopulations in inner-ES for generating better solutions. Two assistant operators, competition and newborn, work together for poor subpopulations elimination and creating new subpopulations. By using two-level ES, MPES is able to obtain multiple good solutions. We test the MPES extensively on benchmarks, and compare it with previous state assignment methods from various aspects. The experimental results show MPES achieved a significant cost reduction of area and power dissipation over the previous publications.