A local cost simulation-based algorithm to solve distributed constraint optimization problems
As an important incomplete algorithm for solving Distributed Constraint Optimization Problems (DCOPs), local search algorithms exhibit the advantages of flexibility, high efficiency and high fault tolerance. However, the significant historical values of agents that affect the local cost and global c...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2023-03-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-1296.pdf |
| _version_ | 1827986935240458240 |
|---|---|
| author | Meifeng Shi Feipeng Liang Yuan Chen Ying He |
| author_facet | Meifeng Shi Feipeng Liang Yuan Chen Ying He |
| author_sort | Meifeng Shi |
| collection | DOAJ |
| description | As an important incomplete algorithm for solving Distributed Constraint Optimization Problems (DCOPs), local search algorithms exhibit the advantages of flexibility, high efficiency and high fault tolerance. However, the significant historical values of agents that affect the local cost and global cost are never taken into in existing incomplete algorithms. In this article, a novel Local Cost Simulation-based Algorithm named LCS is presented to exploit the potential of historical values of agents to further enhance the exploration ability of the local search algorithm. In LCS, the Exponential Weighted Moving Average (EWMA) is introduced to simulate the local cost to generate the selection probability of each value. Moreover, populations are constructed for each agent to increase the times of being selected inferior solutions by population optimization and information exchange between populations. We theoretically analyze the feasibility of EWMA and the availability of solution quality improvement. In addition, based on our extensive empirical evaluations, we experimentally demonstrate that LCS outperforms state-of-the-art DCOP incomplete algorithms. |
| first_indexed | 2024-04-09T23:39:14Z |
| format | Article |
| id | doaj.art-3d96f4794a1244fa82a65fe370bd82f4 |
| institution | Directory Open Access Journal |
| issn | 2376-5992 |
| language | English |
| last_indexed | 2024-04-09T23:39:14Z |
| publishDate | 2023-03-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj.art-3d96f4794a1244fa82a65fe370bd82f42023-03-19T15:05:16ZengPeerJ Inc.PeerJ Computer Science2376-59922023-03-019e129610.7717/peerj-cs.1296A local cost simulation-based algorithm to solve distributed constraint optimization problemsMeifeng Shi0Feipeng Liang1Yuan Chen2Ying He3Department of Computer Science and Engineering, Chongqing University of Technology, Chongqing, ChinaDepartment of Computer Science and Engineering, Chongqing University of Technology, Chongqing, ChinaDepartment of Computer Science and Engineering, Chongqing University of Technology, Chongqing, ChinaDepartment of Computer Science and Engineering, Chongqing University of Technology, Chongqing, ChinaAs an important incomplete algorithm for solving Distributed Constraint Optimization Problems (DCOPs), local search algorithms exhibit the advantages of flexibility, high efficiency and high fault tolerance. However, the significant historical values of agents that affect the local cost and global cost are never taken into in existing incomplete algorithms. In this article, a novel Local Cost Simulation-based Algorithm named LCS is presented to exploit the potential of historical values of agents to further enhance the exploration ability of the local search algorithm. In LCS, the Exponential Weighted Moving Average (EWMA) is introduced to simulate the local cost to generate the selection probability of each value. Moreover, populations are constructed for each agent to increase the times of being selected inferior solutions by population optimization and information exchange between populations. We theoretically analyze the feasibility of EWMA and the availability of solution quality improvement. In addition, based on our extensive empirical evaluations, we experimentally demonstrate that LCS outperforms state-of-the-art DCOP incomplete algorithms.https://peerj.com/articles/cs-1296.pdfDCOPsLCSEWMAInferior solutions |
| spellingShingle | Meifeng Shi Feipeng Liang Yuan Chen Ying He A local cost simulation-based algorithm to solve distributed constraint optimization problems PeerJ Computer Science DCOPs LCS EWMA Inferior solutions |
| title | A local cost simulation-based algorithm to solve distributed constraint optimization problems |
| title_full | A local cost simulation-based algorithm to solve distributed constraint optimization problems |
| title_fullStr | A local cost simulation-based algorithm to solve distributed constraint optimization problems |
| title_full_unstemmed | A local cost simulation-based algorithm to solve distributed constraint optimization problems |
| title_short | A local cost simulation-based algorithm to solve distributed constraint optimization problems |
| title_sort | local cost simulation based algorithm to solve distributed constraint optimization problems |
| topic | DCOPs LCS EWMA Inferior solutions |
| url | https://peerj.com/articles/cs-1296.pdf |
| work_keys_str_mv | AT meifengshi alocalcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT feipengliang alocalcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT yuanchen alocalcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT yinghe alocalcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT meifengshi localcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT feipengliang localcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT yuanchen localcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems AT yinghe localcostsimulationbasedalgorithmtosolvedistributedconstraintoptimizationproblems |