Swarm-Intelligence-Based Optimization Algorithms and Their Applications

ABSTRACT

Swarm intelligence is one of the most popular derivative-free and population-based optimization algorithms. It has been extensively used for both continuous and discrete optimization problems due to its versatile optimization capabilities. In this dissertation, we proposed two swarm-intelligence-based optimization algorithms to solve different problems.

In the first proposed optimization algorithm, we tried to explore the possibility of applying the self-organizing feature maps (SOM) algorithm in continuous optimization problems. A new optimization algorithm based on the self-organizing map was proposed and named SOM-based optimization (SOMO). Via the SOMO algorithm, good solutions to an optimization problem can be simultaneously explored and exploited during the self-organizing process. In addition, the outputs of the neural network allow us to transform a multi-dimensional fitness (objective) landscape into a three-dimensional projected fitness landscape or a two-dimensional fitness image. By viewing the three-dimensional projected fitness landscape or the two-dimensional fitness image we may choose which region deserves to be further exploited. Some test functions and data sets were used to demonstrate the performance of the SOMO algorithm. Two applications based on the SOMO algorithm were proposed. The first application is the SOMO-based recommendation system, which is able to learn personal preferences of users and provide tailored suggestions to users, to help travelers to plan their sightseeing tours. Tourist spots which meet the travelers’ preferences will be suggested by the proposed recommendation system. The second application is the SOMO-based clustering (SOMOC) algorithm, which is able to simultaneously determine the number of clusters and partition a given data set into the estimated number of clusters. The SOMOC algorithm could be used to detect objects with different geometrical properties in images. Some experimental results demonstrate that the SOMOC algorithm could detect clusters with different geometrical shapes.

In the second proposed optimization algorithm, we considered a special puzzle problem where the shape of each puzzle piece is a rectangle. Two different approaches to assemble the special puzzles were proposed. The first method is based on common human heuristics. It is very straightforward but effective for many puzzle problems. For some puzzle problems where the first approach doesn’t work well, the second approach which is based on ACS algorithm can provide appealing solutions. Some images were used to test the proposed methods. In addition, we proposed a new approach to implement a descrambler. The security problem of speech communication has always been a demanding problem in military and business areas. A common approach to realizing end-to-end security is the use of a scrambler. Most of the scramblers are based on the permutation of speech signals in the time domain and/or frequency domain. On the other hand, descramblers are used to eavesdrop information from scrambled speech signals. We treated the descrambling problem as a puzzle solving problem. Some speech signals were used to demonstrate the performance of the proposed methods.

Key Words: swarm intelligence, derivative-free, population-based, optimization algorithm, SOM algorithm, SOMO algorithm, neural network, fitness landscape, recommendation system, clustering algorithm, SOMOC algorithm, puzzle, ACS algorithm, security, speech communication, scrambler, descrambler.

以群體智慧為基礎的最佳化演算法及其應用

摘要

群體智慧(swarm intelligence)是目前廣受歡迎的最佳化(optimization)演算法，其依據族群為基礎以及無需導式的特性深受大眾所喜愛，因為有著多變化且多功能的最佳化特性，使得群體智慧廣泛地使用於許多連續與離散的最佳化問題上，在此論文中，我們提出兩種以群體智慧為基礎的最佳化演算法來解決許多不同的問題，並將其應用在各種不同領域之最佳化問題中。

在第一個所提出的最佳化演算法中，我們嘗試利用「自我特徵組織映射圖(self-organizing feature maps, SOM)演算法」的特性來改良並提出一個解決連續問題的新型態最佳化演算法，此新型態的最佳化演算法我們將其命名為「以自我組織特徵映射圖為基礎的最佳化(SOM-based optimization, SOMO)演算法」，經由此最佳化演算法，對於最佳化問題中的較佳或適合解可以在自我組織的過程中進而同時被探索與開拓；在另外一方面，其類神經網路輸出的特性，提供將多維空間的適應度景觀圖(fitness landscape)轉換至二維或三維空間的適應度景觀圖影像，藉由適應度景觀圖的建立，我們可以選擇適合再繼續探索的區域範圍來搜尋問題的最佳解，在此演算法中我們提出了一些測試方法來展示其效能。接著我們以此演算法提出了兩個應用，第一個應用為以「SOMO為基礎的推薦系統(SOMO-based recommendation system)」，此系統可以學習使用者的喜好，幫助使用者規劃旅行行程並提出適合的旅行行程建議給使用者；第二個應用為「以SOMO為基礎的群聚(SOMO-based clustering, SOMOC)演算法」，此演算法可以同時決定出群聚的數目以及資料的分配方法，其特性在於能正確且有效地偵測影像上各種不同形狀的物件，在此演算法中我們利用一些不同形狀的物件影像來測試及展示其演算法的效能。

在第二個所提出的最佳化演算法中，我們將問題鎖定在解決矩形拼圖(puzzle)的問題上，分別提出兩種不同的方法來組合拼圖，第一個為以啟發式(heuristic)為基礎的方法，此方法能直覺且有效地解決大部分的拼圖問題；然而，針對第一個方法所不能解決的問題，我們提出第二個以「螞蟻演算法(ant colony system, ACS)」為基礎的方法來改善第一個方法，在此問題中我們利用一些影像來測試其演算法的效能。接著我們將此演算法應用於語音通訊保密的語音解攪拌器上，語音通訊保密已經被廣泛應用在軍事與商業領域，一般的作法是將語音攪拌器(scrambler)使用在端點對端點的保密上，而大部分的語音攪拌器都是以時域與頻域為基礎來進行排列攪拌，另一方面語音解攪拌器(descrambler)也必須防止竊聽者盜取攪拌後的語音訊號，在此實驗上，我們將語音解攪拌的問題視為解拼圖的問題，並且利用我們所提出的解拼圖方法來實作其應用，最後我們採用一些範例來展示其結果。

關鍵字：群體智慧、最佳化演算法、自我特徵組織映射圖演算法、以自我組織特徵映射圖為基礎的最佳化演算法、類神經網路、適應度景觀圖、推薦系統、群聚演算法、拼圖、螞蟻演算法、語音通訊保密、攪拌器、解攪拌器。