積木型遺傳規劃法於最佳化組合之應用

Application of Block Type Genetic Programming to Combinatorial Optimization

許聰海(Tsung-Hai Hsu)

指導教授 ： 姚立德

國立臺北科技大學/機電學院/電機工程系所/碩士(2005年)

https://doi.org/10.6841/NTUT.2005.00113

摘要

傳統的遺傳規劃法被設計在搜尋結構解的應用上，利用樹狀結構的交配演化，以得到更好的結構解。但樹狀結構的表示方法複雜，在計算適應值時，重組此樹狀所表示的結構解時會變的相當繁雜。因此，本論文中提出了一個遺傳規劃法全新的結構型態-積木型遺傳規劃法，此新的結構表示上，其具有結構表示簡單與操作容易的優點，在學習的過程中可減少處理的步驟，因此在解決最佳化組合的問題中，可大幅增加其執行效能。
在本研究中將利用三個不同領域的最佳化組合問題，來探討積木型遺傳規劃法的學習成效，其中包括樣本識別中的分類問題、直接負載排程控制規劃與系統建模。
此外，在本研究中，尚且利用基因法則解決需量交易中競價的問題，透過基因法則具有搜尋參數的能力，可對購電價格作最佳化的計算，在最低成本與收購電量兩者之間取得最佳平衡，使得電力業者可以準確地管理能源以及節省因需量交易所花費的成本。

關鍵字

積木型遺傳規劃法 ； 樣本識別 ； 直接負載控制 ； 系統建模 ； 需量交易

並列摘要

Traditional genetic programming (GP) is designed to search the structural solution by utilizing crossover mechanisms of tree structure to get better structures. But the expression method of the genotype structure is complicated, and while calculating the fitness, the recombination process must take many steps to accomplish. Thus, a novel representation scheme called block type genetic programming (BGP) is proposed in this thesis. Since BGP has the advantages of simple representations and easy programming for operations, the steps of genotype operation can be largely reduced and the efficiency in the course of learning is greatly improved.
In this thesis, we will verify the performance of BGP by using three optimization problems. Those problems are pattern recognition, direct load control and system modeling. Moreover, we also use the genetic algorithm (GA) to solve the question of demand exchange. Based on the searching ability of GA, we can find the best unloaded strategy for power users and reduce the cost of the power company.

並列關鍵字

Block Type Genetic Programming ； Pattern Recognition ； Direct Load Control ； System Modeling ； Demand Exchange Management System

參考文獻

1. J. R. Koza, Genetic Programming. Cambridge, MA: MIT Press, 1992.

2. C. Ferreira, “Gene expression programming: A new adaptive algorithm for solving problems,” Complex Systems, vol. 13, no. 2, pp. 87-129, 2001.

3. J. R. Quinlan, C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann, 1993.

4. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.

5. J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, Ann Arbor, MI, 1975.