A Study on Hardware Implementation of a Genetic Algorithm with Adaptive Parameter Adjustment

本研究的目的是开发一种能够在算法执行过程中调整遗传参数值的遗传算法，并适合于硬件实现。1998年，我们开发了一种名为GAA-II的遗传硬件，它根据个体的优越性选择交叉算子和突变率。GAA-II可以作为硬件GA系统的独立核心处理器。它还可以通过连接一组GAA-II芯片来实现并行GA。GAA-II是用Verilog硬件描述语言设计的，并在东京大学VLSI设计与教育中心（VDEC）的芯片制造程序中作为LSI芯片实现。与普通软件GA相比，GAA-II在获得相同结果的情况下，运行速度要快20 ~ 50倍。1999年，我们开发了一个评估板来评估GAA-II芯片。通过对评估板的实验，验证了GAA-II芯片基本功能的正确实现。作为GAA-II的扩展，我们还研究了一种基于分层种群模型的具有自适应参数调整功能的并行遗传算法。在这种并行遗传算法中，在遗传算法执行过程中，子种群之间交换遗传参数，从而在较短的计算时间内获得较好的结果。实验结果表明了所提出的自适应并行遗传算法的有效性。本研究结果已在多个国际和国内会议和研讨会上发表，并作为期刊论文发表。本研究取得了许多卓有成效的成果，为今后遗传算法及其硬件实现的研究提供了有益的参考。

The aim of this research is to develop a genetic algorithm (GA), which is able to adjust the values of genetic parameters during the algorithm execution, and is suitable for hardware implementation.In 1998, we developed a GA hardware called GAA-II, which selected the crossover operators and mutation rates based on the superiority of an individual. GAA-II can be used as a stand-alone core processor of a hardware GA system. It can also be used to implement a parallel GA by connecting a set of GAA-II chips. GAA-II was designed with the Verilog hardware description language, and implemented as an LSI chip in the chip fabrication program of VLSI Design and Education Center (VDEC), the University of Tokyo. Compared with the ordinary software GA, GAA-II runs 20 to 50 times faster than that to get the same results.In 1999, we developed an evaluation board to evaluate the GAA-II chip. From the experiments with the evaluation board, it was confirmed that the basic functions of the GAA-II chip were correctly implemented. As an extension of GAA-II, we also investigated a parallel GA, which had a function of adaptive parameter adjustment, and was based on a hierarchical population model. In this parallel GA, GA parameters were exchanged among subpopulations during the GA execution to obtain good results in a short computation time. Experimental results showed the effectiveness of the proposed adaptive parallel GA.Results obtained in this research were presented in several international and domestic conferences and workshops, and published as journal papers. From this research, many fruitful results have been obtained, which will be useful for future research on genetic algorithms and their hardware implementation.