以行動代理人建構分散式基因演算法平台

Abstract

基因演算法(Genetic Algorithms, GAs)是一種模擬生物演化機制的演算法，透過基因的複製、突變等基本運算，加上一些選擇、淘汰的機制，來產生優質的子代。基因演算法的威力會隨著一些因素而大幅增長，這些因素和計算能力以及記憶體空間大小有很大的關係，分散式基因演算法(Parellal Genetic Algorithms, PGAs)便成為了一個研究重點。在過去，通常都是利用多顆中央處理器或是區域網路數台電腦並行運作來獲取效能，但這些方法所能提昇的效果有限，而這篇論文則將目標轉向擁有無窮運算潛能的網際網路。這篇論文提出一個基於mobile agent (行動代理人)技術且具擴充性與彈性的分散式基因演算法平台基礎架構。整個設計包含了Agent Space的觀念、Gnutella式的資源搜尋、Resource Description Framework (RDF)式的資源描述以及一種使用三種agent來構成多種分散式基因演算法的Dynamic Architechture PGA (daPGA)。透過這些設計，以網際網路作為基因演算法運算平台的構想，將可以跨出最重要的一步。對基因演算法的設計者來說，此平台可以提供龐大計算能源；對基因演算法的研究者來說，此平台是一個過去不曾出現過的研究環境；而對agent世界來說，則為agent們帶來了基本的基因演算法服務。

This work is devoted to provide a future picture of parallel genetic algorithms (PGAs). Genetic algorithms (GAs) are useful for many optimization problems. But the shortcoming is the largely resource consuming. We try to integrate the needs of high speed GAs computing, the computing power of the Internet, and the trend of mobile agent systems into a concept called the Agent Space for GAs (ASGA). The ASGA is designed to support both academic and ordinary purposes. This study propose an architecture in the search style of Gnutella, which is a fully distributed service for sharing resources, to administer the computers in ASGA. This study employs GA RDF (Resource Description Framework) documents to represent GA problems in order to let other agents use the GA services provided by ASGA conveniently. With GA RDF, agents can freely create their own GA resources and won't conflict with each other. Moreover, this study introduces Dynamic Architecture PGA (daPGA) into ASGA to simulate four major types of PGAs including single deme PGA, static demes PGA, overlapping demes PGA, and dynamic demes PGA. Finally, we get an preliminary prototype of ASGA. We believe that the model is effective in utilizing the Internet resources and capable of pushing GA computing to a new level.