基於點對點的分佈式進化演算法求解WTA並在有雜訊的4G網絡上運行

P2P-Based Distributed Evolutionary Algorithms to Solve WTA and Functioning Over Noisy 4G Network

莫希瑞(Mohammad Hikmat Saeed Hilal)

指導教授 ： 袁賢銘

國立交通大學/電機學院/電機資訊國際學位學程/博士(2019年)

摘要

啟發式搜尋法通常需要高計算能力並且需要較長的執行時間，尤其是在需要高質量結果時。使用功能強大的計算機和大型主機可以幫助在合理的執行時間內找到高質量的解決方案，但是這類型計算機相當昂貴。通過多台經濟實惠的計算機來分佈演算程序，有助於在較短的時間內找到高質量的結果，原因是這些計算機可透過協同工作來尋找解決方案。啟發式搜尋法的分佈式實現，需要計算節點之間通信的最佳大小和頻率，而這只能通過實驗找到。因此，本文提出了一種基於點對點的分佈式遺傳算法、粒子群最佳化和人工蜂群等演算法，在武器-目標分配(Weapon-Target Assignment, WTA)問題上的應用
這三種演算法均在分佈式霧和雲環境中實現，我們使用多個樹莓派3代B+型(Raspberry Pie 3 Model B +)，並在4G網絡環境進行通信，而且也已實施在許多谷歌計算引擎(Google Compute Engine)的運算實例上。這些演算法主要被用來尋找武器-目標分配（WTA）問題的實時解決方案，並在執行後10秒內做出分配決策。此外，我們也研究了信息通道雜訊的容忍度，以評估系統在通訊不可靠之戰鬥環境中的適用性。為了能夠最大限度地提高敵方單位的破壞率，並將己方的受害降至最低，要求WTA的結果質量要盡可能地高，並且愈快做出決策愈佳。因此，WTA可以作為評估分佈式演算法的完美基準工具。本論文將對上述三種算法進行比較，以找出哪種算法能從分佈中獲益最多，並且還將總結我們這項應用實施的最佳通信區間。

關鍵字

分佈式演算法 ； 遺傳演算法 ； 粒子群最佳化 ； 人工蜂群 ； 進化演算法

並列摘要

Heuristic search methods often require high computation capabilities and demand long execution time, especially when high quality of results is demanded. Using powerful computers and mainframes can help finding high quality solutions in a reasonable execution time, however, such computers are quite pricey. Distributing the process over multiple, affordable computers can help finding high quality results in short execution time as such computers can cooperate together in finding solutions. Distributed implementation of heuristic search requires determining the optimal size and frequency of communication between computation nodes, this can only be found out through experiments. This thesis presents a Peer-to-Peer based Distributed Genetic Algorithm, Particle Swarm Optimization and Artificial Bee Colony working on Weapon-Target Assignment (WTA). The three algorithms are implemented in a distributed Fog and Cloud environments using multiple Raspberry Pie 3 Model B+ communicating together using 4G network. The algorithms have also been implemented on a number of Google Compute Engine Instances. The algorithms are hired to find real-time solutions for Weapon- Target Assignment (WTA) problem, allocation decisions are made within 10 seconds of execution and tolerance to channel noise has been investigated in order to evaluate the system’s applicability in battle environment where communication can become less reliable. In order to maximize damage of enemy units and minimize damage received, the quality of WTA results are required to be as high as possible and decisions should be made as quick as possible while, therefore, WTA can serve as a perfect benchmarking tool to evaluate distributed algorithms. The thesis will present a comparison between the three mentioned algorithms to find out which algorithm benefits the most from the distribution. The thesis will also conclude the optimal communication interval for our presented implementation

並列關鍵字

Distributed Algorithms ； Genetic Algorithms ； Particle Swarm Optimization ； Artificial Bee Colony ； Evolutionary Algorithms

參考文獻

[1] https://wikipedia.org.

[2] https://www.sfu.ca.

[3] Optimal Weapon Target Assignment Based on an Geometric Approach, volume 46. IFAC proceesings volumes, 2013.

[4] O. Abdoun, J. Abouchabaka, and C. Tajani. Analyzing the performance of mutation oper- ators to solve the travelling salesman problem. arXiv:1203.3099, 2012.

[5] D. H. Ackley. A connectionist machine for genetic hillclimbing. Kluwer Academic Pub- lishers, Boston MA, 1987.