蟻群算法聚類(lèi)分析研究

李曉霞+黨巾濤

[摘 要]蟻群算法是一種基于仿生學(xué)原理的組合優(yōu)化算法，應(yīng)用于旅行商問(wèn)題、二次分配問(wèn)題、車(chē)輛調(diào)度問(wèn)題及網(wǎng)絡(luò)路由設(shè)計(jì)等問(wèn)題。本文將蟻群算法的思想應(yīng)用到聚類(lèi)分析中，并給出了蟻群聚類(lèi)算法的模型和步驟，并進(jìn)行了仿真實(shí)驗(yàn)，得到其最優(yōu)解。

[關(guān)鍵詞]蟻群算法； 聚類(lèi)分析； 蟻群聚類(lèi)算法

中圖分類(lèi)號(hào)：U416.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2016）15-0348-01

引言

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

1 蟻群算法的基本原理

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

2 蟻群算法在聚類(lèi)分析中的應(yīng)用

（1）問(wèn)題提出

一幅圖像中含有多個(gè)物體，在圖像中進(jìn)行聚類(lèi)分析需要對(duì)不同的物體分割標(biāo)識(shí)，如圖3所示，手寫(xiě)了12個(gè)待分類(lèi)樣品，要分成4類(lèi)，如何讓計(jì)算機(jī)自動(dòng)將這12個(gè)物體歸類(lèi)？

（2）構(gòu)造目標(biāo)函數(shù)

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

式中，為第i個(gè)樣品的第p個(gè)屬性，為第j個(gè)類(lèi)中心的第p個(gè)屬性。

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

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

②初始化信息素矩陣。

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

④計(jì)算各類(lèi)中心。計(jì)算每只螞蟻的目標(biāo)函數(shù)，并對(duì)螞蟻按目標(biāo)函數(shù)值排序。

⑤在排序后的螞蟻解集中，將前L個(gè)螞蟻?zhàn)鳛橐粨Q樣品的螞蟻，取L=2，對(duì)要交換的螞蟻實(shí)施局部搜索操作。

⑥更新信息素值。

⑦如果沒(méi)有達(dá)到最大迭代次數(shù)，則轉(zhuǎn)步驟③，否則輸出最優(yōu)類(lèi)解集。

（4）效果圖

參考文獻(xiàn)

[1] 章春芳.自適應(yīng)的并行蟻群算法及其應(yīng)用[D].揚(yáng)州大學(xué)，2006.

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

[3] 劉波.一種利用信息嫡的群體智能聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，30（35）180-182.

作者簡(jiǎn)介

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

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