元智大學資訊管理學系
第二十屆專業實習成果報告
旅行推銷員問題
旅行推銷員問題的描述：假設有5個城市，一個銷售員在知道各城市間距離的情況下，找出最短的拜訪路線，最終回到出發點，看完學長跑程式給我們看之後，知道概念就是拜訪路線不要有交叉路線，交叉必定路徑較長，效率較差。
旅行推銷員問題屬於組合性最佳化問題(Combinatorial Optimization Problem)，組合性問題是考量如何在有限的資源內達到期望之目標。組合性問題可應用在學校的選課系統，假設某位老師不想早上上課，必須將他的課避開早上的時段，有些老師可能偏好早上上課，兩者就可以互相磨合，達到最佳的效益。
帝國演算法(Imperial CompetitiveAlgorithm, ICA)
在 ICA 中，每一個國家（Country）代表一個可能的解，而國家的強弱則由解之優劣定義。根據各國家的興盛，可將國家分為帝國（Imperialist）與殖民地（Colony）此兩大類。每一個殖民地隸屬於某一個帝國之下，而一個帝國與其管轄之所有殖民地則構成為王國（Kingdom）。
每一個殖民地之基本性質會往其所屬帝國之方向移動，以便使殖民地日漸強盛。若殖民地之國力較所屬帝國之國力強盛，則此殖民地會取代原所屬王國之帝國，而原先的帝國則淪為殖民地。
各帝國也會因彼此之間的競爭關係，去奪取最弱帝國之殖民地。當其他的國皆無殖民地時，則此帝國即為 ICA 所搜尋之最佳解。
-
同化作用: 較弱之國家仿效較強盛國家的機制，或改良其機制。
-
競爭作用: 較為強盛之帝國，需併吞其他衰弱之帝國及其殖民地，以致增強自我本身之實力。
運用這兩個作用到排程問題(旅行推銷員問題, TSP)上，統計較佳的排序，找到可行的最佳解，
例如:
1→2→3→4→5
1→3→5→2→4
以目前來看，兩個排序可看出當1這個城市排在第一個位置是較佳的，若加入其他排序並統計，可能又會有不一樣的解，大量的數據會統計出哪個城市該放在哪個位置是比較好的，5個城市彼此互相比較，慢慢統整出一個可行的最佳解，就是帝國演算法中，殖民地慢慢趨向最好的歸屬，最終會出現最強盛的帝國。
K-means分群法
K-means 是J.B.MacQueen於1967年所提出的分群演算法，必須事前設定群集的數量k，然後找尋下列座標的極大值與極小值，以達到分群的最佳化目的。此次研究直接指派當初隨機選取的K座標值當作中心點，與原分群法理念不同之處在於原分群法會指派新的中心點，捨棄原本的K座標。
(1)隨機指派群的核心城市(圖一)
從目前城市X與Y座標的最小值到最大值中 ，隨機選取出K個核心城市，預設K=3。
(2)產生國家(圖二)
計算每個城市與核心城市的距離，比較出該城市與哪個核心城市最近，最近者則屬於那個核心城市。
