- 學位論文
動態非正規基因演算法應用於多目標最佳化平面規劃
Dynamic and Non-Regular Genetic Algorithm for Multi-Objectives Optimization in Floorplanning
摘要
和一般單一目標平面規劃最佳化問題比較起來，考量多目標平面規劃最佳化問題的差異之處是在於解空間的定義。在做單一目標最佳化問題時只會有全域單一最佳解，但是在多目標最佳化問題中則會有一個解集合，我們稱它為派瑞托最佳解集合(Pareto-Optimal set)， 這個解集合是由許多的全域最佳解所組成，在這個解集合裡面的解彼此互為未被支配(non-dominated)，分不出高下優劣。 在此篇論文當中我們所使用的最佳化演算法為基因演算法，使用序列對表示法(sequence pair)來當作染色體的資料結構並加入archive的概念來處理多目標最佳化問題。有別於一般傳統的基因演算法流程，我們捨棄掉交配運算，著重在突變運算部分，加入直交實驗設計於交換(swap)突變運算子中，並結合模擬退火演算法在執行初期接受較差解的概念，期望能跳脫區域最佳解，達到全域最佳解。 傳統基因演算法是先產生固定數量的初始族群，然後去執行接下來的交配以及突變運算。為了增加初始族群解的多樣性，我們產生大量的染色體，從中挑選一小部分的染色體當作初始族群，執行接下來的突變運算。為了提升基因演算法執行效率，隨著世代數的上升，動態調整每世代的突變次數，並根據每次突變後的結果再執行突變次數的微調，以期能減少在不理想的解空間做過多的突變運算。
並列摘要
The multi-objectives optimization problem has a quite different point of view compared with a single objective problem. There is only one global optimum solution in the single objective optimization problem, but there is a set of solutions in multi-objectives optimization problem, called the Pareto-optimal set. This set constitutes global optimum solutions; which are considered to be equally important and non-dominated with each other. This paper describes a genetic algorithm based multi-objectives optimization problem that uses sequence pair as the data structure of chromosomes and incorporates the concept of archive in order to deal properly with the multi-objectives problem. The difference in genetic algorithm between the traditional one and ours is we forsake crossover operation and focus on mutation operation, combining the idea of orthogonal experiment design with swap mutation operator. For the purpose of achieving global optimal, we add the concepts of simulated annealing algorithm that accepting the inferior solutions at the beginning. The first step in the procedure for executing traditional genetic algorithm is to generate the fix number of chromosomes for crossover and mutation operation. For the purpose of expanding a diversity of initial population, we generate a large amount of chromosomes; besides, only have a part of chromosomes will be selected as initial population. In order to increase efficiency of genetic algorithm in searching solution space and significantly decrease the mutation operation in un-ideal region, we dynamically adjust mutation times as generation rise and fine-tune each generation’s mutation times after each mutation operation.