| 摘要註: |
仿生計算在近幾年非常流行,因為它對於解決大部分的優化問題非常有效。雖然其所得到的解決方案並不一定最佳,但其解在實際應用上通常是可以接受的。在仿生計算的策略中,蟻群最佳化和遺傳演算法是很常用的兩種方法。然而,它們使用不同的機制來解決問題。這兩種策略在解決問題時各自有其自身優勢,蟻群最佳化採用螞蟻般的協同搜索行為來找到好的解,而遺傳演算法採用了適者生存的原則以產生答案。因此在本篇論文中,我們嘗試將它們集成在一起,以增加搜索的多樣性,並提高所求解的質量。我們提出了幾種方法。在第一種方法中,蟻群最佳化首先執行,接著遺傳演算法再執行,這兩種策略都以它們自己的機制進行。當達到預定的迭代次數時,這兩種方法就交換各自目前的的數個最佳解,並且重複相同的過程,直到滿足終止條件為止。我們也設計了在此兩種策略所求得的解的不同表達方式之間的轉換。此外,它也可以很容易地從蟻群最佳化修改為遺傳演算法先執行。此外我們也探討上述方法的一些變形,而此執行架構在本質上也非常適合平行化。最後我們做一些實驗來證明所提方法的效能。 Biologically-inspired computing is very popular in recent years since it can solve most of optimization problems very efficiently. Although the solutions obtained are not certainly optimal, they are usually acceptable for real applications. Among the strategies for this type of computing, the ant colony optimization (ACO) strategy and the genetic algorithm (GA) are very commonly used. They, however, use different mechanisms to solve problems. ACO uses the cooperative search of the ant-like behavior to find good solutions, but GA uses the principle of survival to generate answers. Since the two strategies have their own advantages in solving problems, we thus attempt to integrate them to increase the search diversity in this thesis. We expect the solution quality can be raised as well due to more diversity. Several approaches are thus proposed. In the first approach, the ACO is first executed, and then GA. The two approaches are performed in their own mechanisms. When a predefined iteration number is reached, the two approaches exchange a fixed amount of the best individuals to each other, and the same process is repeated until the termination criterion is met. A transformation strategy between the two different representations of solutions is designed as well. Besides, it can be easily modified as GA before ACS. Some variants from the first approach are then proposed. The execution architecture is very suitable for parallelization in nature. Experiments are also made to show the performance of the proposed approach. |