李曉霞+黨巾濤

[摘 要]蟻群算法是一種基于仿生學原理的組合優(yōu)化算法，應用于旅行商問題、二次分配問題、車輛調度問題及網絡路由設計等問題。本文將蟻群算法的思想應用到聚類分析中，并給出了蟻群聚類算法的模型和步驟，并進行了仿真實驗，得到其最優(yōu)解。

[關鍵詞]蟻群算法； 聚類分析； 蟻群聚類算法

中圖分類號：U416.2 文獻標識碼：A 文章編號：1009-914X（2016）15-0348-01

引言

M.Dorigo在1991年提出的蟻群算法是一種基于仿生學原理的組合優(yōu)化算法，它具有其他智能優(yōu)化算法及群體智能算法的優(yōu)點，本文詳細的敘述了蟻群算法的基本思想、原理和理論，并將其應用到聚類分析中，給聚類分析的分類算法提供了更廣闊的思路。

1 蟻群算法的基本原理

蟻群算法是模擬螞蟻覓食的原理設計出的一種群集智能算法。螞蟻在覓食過程中能夠在其經過的路徑上留下一種稱之為信息素的物質，并在覓食過程中能夠感知這種物質的強度，并指導自己行動方向，它們總是朝著該物質強度高的方向移動，因此大量螞蟻組成的集體覓食就表現(xiàn)為一種對信息素的正反饋現(xiàn)象。某一條路徑越短，路徑上經過的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的幾率也就越高，由此構成的正反饋過程，從而逐漸的逼近最優(yōu)路徑，找到最優(yōu)路徑。其模擬的原理圖如下圖所示：

2 蟻群算法在聚類分析中的應用

（1）問題提出

一幅圖像中含有多個物體，在圖像中進行聚類分析需要對不同的物體分割標識，如圖3所示，手寫了12個待分類樣品，要分成4類，如何讓計算機自動將這12個物體歸類？

（2）構造目標函數(shù)

已知模式樣品集{X}有N個樣品和M個模式分類{，j=1，2，...M}，每個樣品有N個特征。以每個模式樣品到聚類中心得距離之和達到最小作為目標函數(shù)，其數(shù)學模型表示為

式中，為第i個樣品的第p個屬性，為第j個類中心的第p個屬性。

（3）實現(xiàn)步驟

①初始化蟻群參數(shù)，包括蟻群數(shù)目、、轉換規(guī)則參數(shù)、信息蒸發(fā)參數(shù)、局部搜索閾值等。

②初始化信息素矩陣。

③所有螞蟻根據(jù)信息素構建解集。

④計算各類中心。計算每只螞蟻的目標函數(shù)，并對螞蟻按目標函數(shù)值排序。

⑤在排序后的螞蟻解集中，將前L個螞蟻作為要交換樣品的螞蟻，取L=2，對要交換的螞蟻實施局部搜索操作。

⑥更新信息素值。

⑦如果沒有達到最大迭代次數(shù)，則轉步驟③，否則輸出最優(yōu)類解集。

（4）效果圖

參考文獻

[1] 章春芳.自適應的并行蟻群算法及其應用[D].揚州大學，2006.

[2] 胡建軍，唐常杰等基于最近鄰優(yōu)先的高效聚類算法[J].四川大學學報（工程科學版），2004，36（6）.

[3] 劉波.一種利用信息嫡的群體智能聚類算法[J].計算機工程與應用，2004，30（35）180-182.

作者簡介

李曉霞，女，山西省大同市人，碩士研究生學歷，信息與通信工程專業(yè)。

黨巾濤，男，山西省運城市人，碩士研究生學歷，信息與通信工程專業(yè)。