問題：P?Center問題

P?Center問題

摘要

問題：從一個點集合中選擇p個點作為中心點，并把其余分配到某個選擇點，使得

全部點到其對應中心點距離加起來最小。

針對問題，分析得出p-center問題實質為選址問題。其研究背景為工廠選址，屬于

運籌學中經典問題之一。利用智能算法中模擬退火隨機局域搜索算法進行求解最小值。

詳細步驟為：因為題目中未提供點集合，所以首先經過文件查閱⑴和生活實際得到可靠

二維數據點分布，即表示一個點集合，存放方式為文件存放（data.txt）；其次加載點集

合數據，采取模擬退火算法隨機局域搜索算法⑵進行處理：

1）初始化：中心點個數夕=4,溫度7=1000,溫度縮減系數a=0.999,最大

迭代次數Iter—200。

解釋：因為P-Center問題是以工廠選址問題，加上編寫二維數據分布情況，所

以建立工廠數量為事先已知條件，即夕=4；初試溫度設置是影響搜索性能主要

原因之一。初始化溫度高，則搜索到全局最優值可能性大，但計算時間大幅度增

力口；反之，縮短了計算時間，但性能并不優越。所以采取數次試驗方式確定溫度

T=1000；為了確保較大搜索空間，所以讓系數靠近于1；經過數次試驗，確

定迭代次數=200,此時結果較為理想。

2）迭代葉二200次，循環第三步到第四步。

3）從臨域中選擇最好解，即確定最優值：產生新值才_〃。獷=x+Ax；增量

Af=f（x_new）-f{x}；若AF>0,則接收作為新解，否者以概率

exp（-△//（奴））接收〃郵作為新解。

4）T逐步降低，且7>rn,最終跳至第二步。

5）得到距離最小值

然后經過模擬退火局部搜索算法，得迭代情況為:

?an)oox>o

?1上?

最終經過模擬退火局部搜索算法，得出分配圖為:

得出四個粗五角星為各自中心點，其中顏色相同屬于各自顏色中心點，即相同顏色距離

各自中心點最短。經過Python得出最近距離為：102.

問題擴充：針對P-Center問題，還能夠經過k-means聚類算法⑶進行處理，得到與

最近搜索算法?樣結果。

關鍵詞：P-Center選址問題模擬退火隨機局域搜索算法K-Means聚類算法

目錄

P-Center問題1

摘要1

1問題重述5

2數據預處理5

2.1數據來源5

2.2數據預處理方法5

2.3數據選取參考原則6

3問題分析6

3.1問題6

4問題假設6

5符號說明7

6模型的建立與求解7

6.1解法一8

6.1.1模擬退火隨機局部搜索算法8

6.1.2算法求解9

6.2解法二12

6.2.1K-Means聚類算法12

6.2.2算法求解12

7模型的評價13

8參考文獻14

附錄14

附錄一模擬退火隨機局域搜索算法Python代碼15

附錄一聚類算法Python代碼20

附錄三迭代次數與目標函數關系28

附錄四結論圖42

1問題重述

選址問題是運籌學中經典問題之一。經典選址問題包含連續選址問題、離散選址問

題、P-Median問題以及P-Center問題等。該問題屬于P-Center問題，從一個點集合中

選擇P個點作為中心點，并把其余點分配到某個選擇點，使得全部點到其對應中心點距

離加起來最小。

2數據預處理

注：數據存放形式為:data.txt,可在附件一中查看

2.1數據起源

（1）文件查閱

（2）生活實際

2.2數據預處理方法

（1）數據選取：去除無效數據以及噪聲數據。

（2）數據整合：將若干個數據庫整合成一個數據存放結構。

（3）數據代替：將雜亂數據代替成易處理數據。

（4）數據變換：將原始數據轉換為適合任務定價形式。

2.3數據選取參考標準

（1）統一數據源編碼。

（2）去除唯一屬性。

（3）去除重復屬性。

（4）去除可忽略字段。

（5）深入處理：去除異常數據，去除附帶噪聲數據，填充空缺值、丟失值。

3問題分析

3.1問題

首先，經過文件查閱和生活實際得到可靠二維數據點分布，將此二維分布作為數據點集

合，然后經過模擬退火最近搜索算法⑷進行迭代優化，最終得到全部點到其中心點距離。

4問題假設

L假設依照數據特征或者政策（比如工廠政策）確定，即已經確定P-Cente「中p中心

個數。

2.假設點集合為二維集合，不包含任何三維或者多維信息。

5符號說明

6模型建立與求解

選址問題現在有多個求解方法，大致分為定性和定量兩類：定性方法主要是結合層次分

析法和含糊綜正當對各方案進行指標評價，最終得出最優選址；定量方法主要是松弛算

法和啟發式算法以及二者結合。而本題處理是P-Center問題，即使用啟發式算法-智能

算法模擬退火隨機局部搜索算法⑸進行處理。

6.1解法

6.1.1模擬退火隨機局部搜索算法

模擬退火算法是一個貪心算法，不過其搜索過程引入了隨機原因。在迭代更新可行解時,

以一定概率來接收一個比當前解要差解，所以有可能會跳出局部最優解，達成全局最優

解，其搜索原理以下列圖：

圖1模擬退火隨機局部搜索算法示意圖

假定當前可行解為x,迭代更新后解為＞new,那么對應〃能量差〃定義為:

△f=f(x_new)—f(x)

以對應概率接收新值，此概率為:

exp(-孝)最小值優化問題

夕(Af)=K1

exp(^)最大值優化問題

模擬退火隨機局域搜索算法思緒為:

圖2模擬退火隨機局域搜索算法思緒圖

6.1.2算法求解

注：詳細Python程序見附錄一與附件一

依照算法思想，經過Python得到迭代與目標函數關系為:

180-

17o

16o

r5o

W

*

14

嗎o

生

HL3o

L2o

11O

100-,,

6i5075100125150175200

速代次發

圖3模擬退火訓練曲線圖

能夠看出經過200次迭代，優化目標函數處于相對穩定狀態。詳細目標函數與迭代次數

對應關系見附錄，以下為部分對應關系：

第186次迭代:目標函數=186,193903261

第187次迭代:目標函數=215.784785022

第188次迭代:目標函數=186.998732666

第189次迭代:目標函數=166.417149078

第190次迭代:目標函數=224,515369868

第191次迭代:目標函數=240,503650114

第192次迭代:目標函數=224,599534187

第193次迭代:目標函數=245,57430458

第194次迭代:目標函數=331,210864乃8

第195次迭代,目標函數=236.657697786

第196次迭代:目標函數=244.844816837

第197次迭代:目標函數=238,634981095

第198次迭代:目標函數=267,60921475

第199次迭代:目標函數=231,441025132

圖4部分迭代次數與目標函數關系

最終得出點集合分配圖為:

圖5點集合分配圖

得出四個粗五角星為各自中心點，其中顏色相同屬于各自顏色中心點，即相同顏色距離

各自中心點最短。經過Python得出最近距離為：102.

6.2解法二

經過智能算法中模擬退火隨機局域搜索算法能夠得出對應結論，為了檢驗以及去探索更

多處理方式，使用了聚類算法，以下為模型以及過程。詳細Python代碼見附錄二以及

附件一。

6.2.1K-Means聚類算法

算法過程以下：

1）從N個點中隨機選取p個點作為中心點

2）對剩下點測量到其每個中心點距離，并把它歸到中心點類

3）重新計算已經得到各個類中心點

4）迭代第二步、第三步直至新中心點與原中心點相等或者小于指定閾值，算法結束

6.2.2算法求解

經過Python程序將經過文件查找點集合數據data.txt進行聚類分析，得到與局域搜索算

法類似分配圖，以下列圖所表示:

Distributiondiagram

圖6聚類分析分配圖

此圖解釋與模擬退火隨機局域搜索算法相同，不再重復解釋。

一樣能夠得出全部點到對應中心點距離最小為：102.。

7模型評價

7.1模型優缺點

模型優點:

（1）經過模擬退火隨機局域搜索算法應用十分廣泛，能夠高效處理NP完全問題

（2）模擬退火隨機搜索算法與K-Means聚類算法相互結合，相互印證，使得數據

準確性得以確保。

（3）經過模擬退火算法與K-Means算法得出點集合分配圖能夠形象生動得出二維

數據關系.

模型缺點:

(1)模擬退火隨機局域搜索算法初始化設置必須準確，要經過數次試驗才能得到

適宜初始化值。

8參考文件

[1]CCEHC:Anefficientlocalsearchalgorithmforweightedpartialmaximum

satisfiability,ArtificialIntelligence,z

[2]LocalSearchforMinimumWeightDominatingSetwithTwo-LevelConfigurationChecking

andFrequencyBasedScoringFunction,JournalofArtificialIntelligenceResearch(JAIR),,

⑶王守強.多中心點聚類問題隨機算法[D].山東大學,.

⑷朱泓丞.設施選址問題研究與應用[D].中國科學技術大學,.

⑸蔣建林,徐進澎，文杰.基于單親遺傳模擬退火算法頂點P-中心問題[J].系統工程學

報〃26(03):414-420.

附錄

注：詳細代碼見附件

附錄一模擬退火隨機局域搜索算法Python代碼

importnumpyasnp

importmatplotlib.pyplotaspit

importmatplotlib

importscipy.spatial.distanceasDS

importrandom

zandaoguangfont=matplotlib.font_manager.FontProperties(fname='a.TTF')

deff(x):

min

目標函數，全部點到中心點距離和

:paramx:list表示中心點序號

:paramdataSet:數據集

:return:

min

distances=DS.cdist(dataSet,dataSet[x,:])#用于計算兩個輸入集合距離

M二np.min(distances,axis=l)#得出附近點到中心點最小值

retumsum(M)#將最小值累加得到最小距離

deffind_next(x):

min

從鄰域中選擇最好解

:paramx:

:paramdataSet:

:return:最優值

min

ind=random.sample(range(p)/l)

x_new=list.copy(x)

tmp:random.sample(range(dataSet.shape[0]),l)#dataSet.shape[0]返回行數

whiletmp[O]inx:

tmp=random.sample(range(dataSet.shape[O]),1)

x_new[int(ind[O])]=tmp[O]

iff(x_new)<f(x):

returnx_new

else:

ifrandom.random()<np.exp(-(f(x_new)-f(x))/T):#模擬退火算法關鍵

returnx_new

else:

returnx

#得到數據

print("第一步：加載數據")

dataSet=[]

fileln=open('data.txt')

forlineinfileln.readlines():

lineArr=line.strip().split('')

dataSet.append([float(lineArr[0]),float(lineArr[-l])])

dataSet=np.array(dataSet)

p=4#設定問題p中心參數值

T=1000#模擬退火初始溫度

a=0.999#溫度降低系數，為了確保較大搜索空間，所以非常靠近于1

lter=200#最大迭代次數

#模擬退火

#param:history統計距離和最優值，方便比較最小值

#param:best_x統計當前距離和最小值

x二random.sample(range(dataSet.shape[0]),p)#隨機產生初始解

best_x=x

history=[]

foriinrange(lter):

print(,第％d次迭代：目標函數二%5'%(行僅)))

x=find_next(x)

T*=a

iff(x)<f(best_x):

best_x=x

history.append(f(best_x))

print('距離和最小為％s'%f(best_x))

#模擬退火局部搜索訓練曲線圖

#resul:t得出模擬退火迭代次數與目標函數值關系

plt.figure(O)

plt.plotfrangefljter+lj^istory/r-1)

plt.xlabel('迭代次數fontproperties二zandaoguangfont)

plt.ylabelf目標函數值',fontproperties=zandaoguangfont)

plt.title('模擬退火訓練曲線圖,,fontproperties:zandaoguangfont)

#數據分配圖

#用紅藍黃綠等顏色代表p中心中p類

#其中經過搜索后p個中心點用markersize=10五邊形表示

#相同顏色點相比較與相同顏色加粗markersize=10五邊形，即相同顏色以相同顏色加粗

五邊形為中心，此時距離最近。

plt.figure(l)

distances=DS.cdist(dataSet,dataSet[best_x,:])

sorted_dist=np.argsort(distances,axis=l)

color=['r.7b.,；y.,；g.']

colo^I'rp'/bp'/yp'/gp']

foriinrange(p):

ind=sorted_dist[:,0]==i

plt.plot(dataSet[ind,0],dataSet[ind,lLcolor[i])

plt.plot(dataSet[best_x[i],0]/dataSet[best_x[i]/l]/Color0[i],markersize=10)

plt.title('分配圖)fontproperties:zandaoguangfont)

plt.showf)

附錄二聚類算法Python代碼

fromnumpyimport*

importmatplotlib.pyplotaspit

importKMeans

##得到數據…

print("第一步：加載數據…,,)

dataSet=[]

fileln=openf'data.txt")

forlineinfileln.readlines():

temp=[]

lineArr=line.strip().split('\t')

temp.append(float(lineArr[0]))

temp.append(float(lineArr[l]))

dataSet.append(temp)

fileln.closed

##進行聚類…

print(“第二步：進行聚類…”)

dataSet=mat(dataSet)

#設置為4個中心點

k=4

#調用KMeans文件中定義kmeans方法。

centroids,clusterAssment=KMeans.kmeans(dataSetzk)

##第三步：顯示結果…

#數據分配圖

#用不一樣種顏色代表p中心中p類

#其中經過搜索后p個中心點用markersize=10五邊形表示

#相同顏色點相比較與相同顏色加粗markersize=10五邊形，即相同顏色以相同顏色加粗

五邊形為中心，此時距離最近。

print（"第三步：顯示結果…"）

KMeans.showClusterfdataSet,k,centroids,clusterAssment）

Kmeans.py

#################################################

#kmeans:k-meanscluster

#Author:ZanDaoguang

#Date:/03/09

#HomePage:

#Email:

#################################################

fromnumpyimport*

importtime

importmatplotlib.pyplotaspit

#calculateEuclideandistance

defeuclDistance(vectorl,vector2):

returnsqrt(sum(power(vector2-vectorl,2)))#求這兩個矩陣距離，vector1、2均為

矩陣

#initcentroidswithrandomsamples

#在樣本集中隨機選取k個樣本點作為初始質心

definitCentroidstdataSet,k):

numSamples,dim=dataSet.shape#矩陣行數、列數

centroids=zeros((k,dim))#感覺要不要你都能夠

foriinrange(k);

index=int(random.uniform(0,numSamples))#隨機產生一個浮點數，然后將其

轉化為int型

centroidsli,:]=dataSet[indexz:]

returncentroids

#k-meanscluster

#dataSet為一個矩陣

#k為將dataSet矩陣中樣大分成k個類

defkmeans(dataSetzk):

numSamples=dataSet.shape[O]#讀取矩陣dataSet第一維度長度，即取得有多少個

樣本數據

#firstcolumnstoreswhichclusterthissamplebelongsto,

#secondcolumnstorestheerrorbetweenthissampleanditscentroid

clusterAssment=matfzerosffnumSamples,2)))#得到一個N*2零矩陣

clusterChanged=True

##step1:initcentroids

#在樣本集中隨機選取個樣本點作為初始質心

centroids=initCentroids(dataSetyk)k

whileclusterChanged:

clusterChanged=False

##foreachsample

foriinrange(numSamples):#range

minDist=100000.0

minindex=0

##foreachcentroid

##step2:findthecentroidwhoisclosest

#計算每個樣本點與質點之間距離，將其歸內到距離最小那一簇

forjinrange(k):

distance=euclDistance(centroids[j,dataSet[i,:])

ifdistance<minDist:

minDist=distance

minindex=j

##step3:updateitscluster

#k個簇里面與第i個樣本距離最小標號和距離保留在clusterAssment中

#若全部樣本不在改變，則退出while循環

ifclusterAssment[i,0]!=minindex:

clusterChanged=True

clusterAssment[i,:]=minindex,minDist**2#兩個**表示是minDist平方

##step4:updatecentroids

forjinrange(k):

#clusterAssment[:,O].A==j是找出矩陣clusterAssment中第一列元素中等于j

行下標，返回是一個以array列表，第一個array為等于j下標

pointsInCluster=dataSetlnonzerofclusterAssmentf:,0].A==j)[0]]#將dataSet

矩陣中相對應樣本提取出來

centroids。，:]=mean(pointslnCluster,axis=0)#計算標注為j全部樣本平均

值

print(,聚類完成！)

returncentroids,clusterAssment

#showyourclusteronlyavailablewith2-Ddata

Centroids為k個類別，其中保留著每個類別質心

#clusterAssment為樣本標識，第一列為此樣本類別號，第二列為到這類別質心距離

defshowClusterfdataSet,k,centroids,clusterAssment):

numSamples,dim=dataSet.shape

ifdim!=2:

print("Sorry!Icannotdrawbecausethedimensionofyourdataisnot2!")

rpturn1

；；，A

mark=['or','ob','og'okr'z'+^'sr','dr\'<r'z'pr']

ifk>len(mark):

print("對不起，您輸入k太大了，請聯絡管理員山東科技大學咎道廣")

return1

#drawallsamples

foriinrange(numSamples):

markindex=int(clusterAssment[i,0])#為樣本指定顏色

plt.plot(dataSet[i,0],dataSet[i,1],mark[marklndex])

mark=「Dr','Db'JDg','Dk‘，"bj+b','sb'Jdb','<b'Jpb']

#drawthecentroids

foriinrange(k):

plt.plot(centroids[i,0],centroids[i,1],mark[i],markersize=10)

plt.title('Distributiondiagram')

plt.show()

附錄三迭代次數與目標函數關系

第。次迭代：目標函數二179.

第1次迭代：目標函數二205.

第2次迭代：目標函數二179.

第3次迭代：目標函數二190.

第4次迭代：目標函數二186.

第5次迭代：目標函數二255.

第6次迭代：目標函數二237.

第7次迭代：目標函數二360.

第8次迭代：目標函數二235.13584001

第9次迭代：目標函數二245.

第10次迭代：目標函數二247.

第11次迭代：目標函數二273.

第12次迭代：目標函數二280.

第13次迭代：目標函數二280.

第14次迭代：目標函數二198.

第15次迭代：目標函數二195.

第16次迭代：目標函數二277.82403

第17次迭代：目標函數二292.

第18次迭代：目標函數二190.

第19次迭代：目標函數二191.

第20次迭代：目標函數二123.

第21次迭代：目標函數二190.

第22次迭代：目標函數二189.

第23次迭代：目標函數二187.

第24次迭代：目標函數二187.

第25次迭代：目標函數二216.

第26次迭代：目標函數二264.

第27次迭代：目標函數二264.

第28次迭代：目標函數二181.

第29次迭代：目標函數二122.

第30次迭代：目標函數二186.

第3次迭代:目標函數二256.

第32次迭代：目標函數二237.

第33次迭代：目標函數二191.

第34次迭代：目標函數二216.

第35次迭代：目標函數二147.

第36次迭代:目標函數二222.

第37次迭代:目標函數二215.

第38次迭代：目標函數二204.

第39次迭代：目標函數二197.

第40次迭代：目標函數二188.

第41次迭代：目標函數二265.

第42次迭代：目標函數二163.

第43次迭代：目標函數二162.

第44次迭代：目標函數二164.

第45次迭代：目標函數二161.

第46次迭代：目標函數二204.73869345

第47次迭代：目標函數二162.

第48次迭代：目標函數二178.51942545

第49次迭代：目標函數二173.

第50次迭代：目標函數二169.

第51次迭代:目標函數二168.

第52次迭代：目標函數二245.

第53次迭代：目標函數二169.

第54次迭代：目標函數二116.

第55次迭代：目標函數二171.

第56次迭代：目標函數二167.

第57次迭代：目標函數二163.

第58次迭代:目標函數二167.

第59次迭代：目標函數二186.81606983

第60次迭代：目標函數二173.

第61次迭代:目標函數二171.

第62次迭代：目標函數二165.

第63次迭代：目標函數二171.

第64次迭代：目標函數二258.

第65次迭代：目標函數二300.

第66次迭代：目標函數二245.

第67次迭代：目標函數二158.

第68次迭代：目標函數二181.

第69次迭代：目標函數二190.

第70次迭代：目標函數二245.

第71次迭代：目標函數二187.41644075

第72次迭代：目標函數二185.

第73次迭代：目標函數二192.

第74次迭代：目標函數二203.

第乃次迭代：目標函數二179.

第76次迭代：目標函數二176.

第77次迭代：目標函數二177.

第78次迭代：目標函數二261.

第79次迭代：目標函數二186.

第80次迭代：目標函數二111.

第81次迭代:目標函數二164.

第82次迭代：目標函數二199.

第83次迭代：目標函數二201.

第84次迭代：目標函數二200.

第85次迭代：目標函數二226.

第86次迭代:目標函數二162.

第87次迭代：目標函數二180.

第88次迭代：目標函數二186.

第89次迭代：目標函數二184.

第90次迭代：目標函數二175.

第91次迭代：目標函數二134.

第92次迭代：目標函數二188.

第93次迭代：目標函數二178.

第94次迭代：目標函數二179.

第95次迭代:目標函數二244.

第96次迭代：目標函數二170.

第97次迭代：目標函數二251.

第98次迭代：目標函數二170.

第99次迭代：目標函數二263.

第100次迭代：目標函數=266.

第101次迭代：目標函數二233.

第102次迭代：目標函數二236.

第103次迭代：目標函數二225.

第104次迭代：目標函數二256.

第105次迭代：目標函數二253.

第106次迭代：目標函數二192.

第107次迭代：目標函數二178.

第108次迭代：目標函數二181.81273764

第109次迭代:目標函數二209.9163263

第110次迭代:目標函數二213.

第111次迭代：目標函數二188.

第112次迭代:目標函數二123.

第113次迭代：目標函數二105.

第114次迭代：目標函數二170.

第115次迭代：目標函數二162.

第116次迭代：目標函數二202.

第117次迭代：目標函數二208.

第118次迭代：目標函數二199.

第119次迭代:目標函數二147.2914882

第120次迭代:目標函數二209.

第121次迭代:目標函數二188.

第122次迭代:目標函數二254.

第123次迭代:目標函數二182.

第124次迭代:目標函數二232.

第125次迭代:目標函數二169.

第126次迭代:目標函數二170.

第127次迭代:目標函數二188.

第128次迭代:目標函數二102.

第129次迭代:目標函數二186.11050464

第130次迭代:目標函數二188.60993634

第131次迭代:目標函數二275.

第132次迭代：目標函數二362.

第133次迭代：目標函數二270.

第134次迭代：目標函數二250.

第135次迭代：目標函數二240.15223

第136次迭代：目標函數二194.

第137次迭代：目標函數二159.9543548

第138次迭代：目標函數二113.

第139次迭代：目標函數二197.

第140次迭代:目標函數二188.

第141次迭代：目標函數二209.

第142次迭代：目標函數二177.

第143次迭代：目標函數二177.

第144次迭代：目標函數二177.

第145次迭代：目標函數二177.

第146次迭代：目標函數二123.

第147次迭代：目標函數二178.

第148次迭代：目標函數二181.

第149次迭代：目標函數二180.

第150次迭代:目標函數二179.

第151次迭代:目標函數二179.

第152次迭代:目標函數二178.

第153次迭代:目標函數二267.

第154次迭代:目標函數二177.

第155次迭代:目標函數二184.

第156次迭代:目標函數二255.

第157次迭代:目標函數二249.

第158次迭代:目標函數二307.

第159次迭代:目標函數二250.

第160次迭代:目標函數二196.

第161次迭代:目標函數二196.

第162次迭代：目標函數=209,33031066

第163次迭代：目標函數二204.

第164次迭代：目標函數=211.

第165次迭代：目標函數二149.

第166次迭代：目標函數二192.

第167次迭代：目標函數二140.

第168次迭代：目標函數二181.94000428

第169次迭代:目標函數二160.

第170次迭代:目標函數二160.

第171次迭代：目標函數二110.

第172次迭代:目標函數二115.

第173次迭代:目標函數二114.

第174次迭代:目標函數二114.

第175次迭代:目標函數二196.53638158

第176次迭代:目標函數二212.

第177次迭代：目標函數二191.

第178次迭代：目標函數二202.

第179次迭代：目標函數二180.

第180次迭代：目標函數二280.

第181次迭代：目標函數二177.

第182次迭代：目標函數二277.

第183次迭代：目標函數二284.

第184次迭代:目標函數二178.

第185次迭代：目標函數二186.85188453

第186次迭代：目標函數二186.

第187次迭代：目標函數二215.

第188次迭代:目標函數二186.

第189次迭代:目標函數二166.

第190次迭代:目標函數二224.

第191次迭代:目標函數二240.

第192次迭代：目標函數二224.

第193次迭代：目標函數二245.57430458

第194次迭代：目標函數二331.

第195次迭代：目標函數二236.

第196次迭代：目標函數二244.

第197次迭代：目標函數二238.

第198次迭代：目標函數=267.60921475

第199次迭代：目標函數二231.

距離和最小為102.4019743

附錄四結論圖

O

18

l7O

6

lO

r5O

lO

4

愫

#LO

H3

L2O

l1O

l0O

02550T5100125150175200

速代次數

圖7模擬退火迭代訓練曲線圖

分配?四

04

圖8模擬退火隨機局域搜索算法分配圖

Distributiondiagram

圖9聚類算法分配圖

C++代碼

#include<iostream>

#include<algorithm>

#include<string>

#include<math.h>

#include<fstream>

#include<vector>

#include<iomanip>

#include<sstream>

#include<time.h>

#defineMAXle9

usingnamespacestd;

structpoint{

doublex;

doubley;

}；

inip=4,T=1000,Iler=200;

doublea=0.999;

vector<point>dataset;

doublegetdis(pointpl,pointp2)

returnsqrt(pow((pl.x-p2.x),2)+pow((pl.y-p2.y),2));

)

doublef(vector<int>x)

doublesum=0;

vector<vector<double?dis;

dis.resize(4);

for(inti=0;i<4;i++)

dis[i].resize(dataset.size());

for(inti=0;i<dataset.sizef);i++)

{

dis[0][i]=getdis(dataset[i]zdataset[x[0]]);

dis[l][i]=geldis(ddlasel[i]Adaldbet[x[l]]);

dis[2][i]=getdis(dataset[i]zdataset[x[2]]);

dis[3][i]=getdis(dataset[i]zdataset[x[3]]);

)

vector<double>mindis;

doublemin;

for(inti=0;i<dataset.size();i++)

min=dis[O][i];

if(min>dis[l][i])min=dis[l][i];

if(min>dis[2][i])min=dis[2][i];

if(min>dis[3][i])min=di