promotion image of download ymail app
阿隆 發問時間: 科學工程學 · 1 0 年前







粒子群最佳化演算法(Particle Swarm Optimization, PSO)於1995年,由學者Kennedy與Eberhart所提出的一種巨集啟發式演算法。


其中,旅行銷售員問題(Traveling Salesman Problem, TSP)為一典型最佳化問題,已被許多專家學者證實為一NP-Complete問題。此方面的研究相當廣泛,例如電路板元件的佈線、物流路線規劃等,皆可利用旅行銷售員問題的概念來求解。

本文以粒子群最佳化演算法,透過轉換空間機制(Transfer Space, TS)處理實數編碼問題。為了避免粒子過早收斂而陷入區域最佳解,因此採用模擬退火(Simulated Annealing, SA)進行區域搜尋,讓粒子有能力跳脫區域最佳解的限制,故本文提出一種新的方法稱為XXX-XX-XX演算法。

並且嘗試以模糊分群(Fuzzy C-mean Clustering, FCM)演算法作為求解大型旅行銷售員問題之分群方法。經過實驗測試與相關文獻進行比較,結果顯示本文所提出的方法,在未分群的情況下,求解五十個以內的城市問題有相對較佳之求解能力,而透過分群的方式求解大型旅行銷售員問題,有助於降低求解誤差率、運算時間、複雜度。



Particle Swarm Optimization (PSO) is a new developed heuristic algorithm by Eberhart and Kennedy in 1995.




2 個解答

  • 妮妮
    Lv 5
    1 0 年前

    Particle Swarm Optimization algorithm (Particle Swarm Optimization, PSO) in 1995, by the scholars of the Kennedy and Eberhart proposed a heuristic algorithm macro.

    There are a number of relevant documents to prove the continuity of PSO in the optimization problem, quite a good search capability. In the discrete issues, such as scheduling, assigning, etc., there are many documents to PSO to solve this problem.

    Among them, the travel salesman problem (Traveling Salesman Problem, TSP) is a typical optimization problem, many experts and scholars have been confirmed to be an NP-Complete problem. This study a wide range of components such as printed circuit boards routing, logistics, route planning, traveling salesman can use the concept to solve the problem.

    In this paper, particle swarm optimization algorithm, through the mechanism of the conversion space (Transfer Space, TS) to deal with the issue of real-coded. Particles in order to avoid premature convergence and the optimal solution in the region, so the use of simulated annealing (Simulated Annealing, SA) for the regional search, the ability to allow particles beyond the optimal solution of the restricted region, so this paper a new method known as the XXX algorithm-XX-XX.

    And try to fuzzy clustering (Fuzzy C-mean Clustering, FCM) algorithm for solving large traveling salesman problem of clustering methods. After experimental testing and comparison of the relevant literature showed that the method proposed in this article, in the absence of clustering of cases, 50 days to solve the urban problems of solving a relatively better capacity, and through the cluster approach for solving large traveling salesman problem , help to reduce the error rate of solving, computation time, complexity.

    • Commenter avatar登入以對解答發表意見
  • 1 0 年前

    The grain of subgroup optimization calculating method (Particle Swarm Optimization, PSO) in 1995, one great collection heuristic calculating method which proposed by scholar Kennedy and Eberhart. Had many related literature to prove that PSO in the continuous optimization question, has the quite outstanding search ability. But is leaving the divergence question, for example row of regulation, designation and so on, also many literature solve this aspect problem by PSO. And, the travel seller question (Traveling Salesman Problem, TSP) is a model optimization question, already by many experts confirmation was a NP-Complete question. This aspect's research is quite widespread, for example the circuit wafer part's wiring, the physical distribution route plan and so on, all may solve using the travel seller question concept. This article by the grain of subgroup optimization calculating method, by the transformation space mechanism (Transfer Space, TS) deals with the real number code issue. In order to avoid granule premature restraining falling into the region best solution, therefore uses the simulation annealing (Simulated Annealing, SA) carries on the region search, lets the granule have ability bracelet region best solution limit, therefore this article proposed that one new method is called the XXX-XX-XX calculating method. And attempts by hives off fuzzily (Fuzzy C-mean Clustering, FCM) the calculating method hives off the method as the solution large-scale travel seller question. Tests after the experiment with is related the literature to carry on the comparison, finally demonstrated this article proposed method, in has not hived off in the situation, solves 50 within the urban questions to have the relatively good solution ability, but by hives off the way solves the large-scale travel seller question, is helpful in cuts the solution error coefficient, the operation time, the order of complexity.

    參考資料: 自己、奇摩翻譯網
    • Commenter avatar登入以對解答發表意見