In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movemen...In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.展开更多
In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s phe...In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s pheromone trails and reinforcing trails at best paths until eventually a single path is followed. On the other hand, RFD is based on copy- ing how drops form rivers by eroding the ground and de- positing sediments. In a rough sense, RFD can be seen as a gradient-oriented version of ACt. Several previous experi- ments have shown that the gradient orientation of RFD makes this method solve problems in a different way as ACt. In particular, RFD typically performs deeper searches, which in turn makes it find worse solutions than ACt in the first exe- cution steps in general, though RFD solutions surpass ACt solutions after some more time passes. In this paper we try to get the best features of both worlds by hybridizing RFD and ACt. We use a kind of ant-drop hybrid and consider both pheromone trails and altitudes in the environment. We apply the hybrid method, as well as ACt and RFD, to solve two NP-hard problems where ACt and RFD fit in a different manner： the traveling salesman problem （TSP） and the prob- lem of the minimum distances tree in a variable-cost graph （MDV）. We compare the results of each method and we an- alyze the advantages of using the hybrid approach in each case.展开更多
This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP-hard problem can be converted into concave maximization dual problems witho...This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP-hard problem can be converted into concave maximization dual problems without duality gap. And the dual problems can be solved, under certain conditions, by polynomial algorithms.展开更多
Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and ...Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.展开更多
The layout optimization for the dishes installed on a rotating table is investigated. This is a packing problem with equilibrium behavioural constraints. To deal with its layout topo-models and initial layout, a mathe...The layout optimization for the dishes installed on a rotating table is investigated. This is a packing problem with equilibrium behavioural constraints. To deal with its layout topo-models and initial layout, a mathematical model and heuristic approaches, including the method of model-changing iteration (MCI) and the method of main objects topo-models (MOT), are proposed, with a series of intuitive algorithms embedded in, such as the technique for the search under the initial guess and the strategies for remission of "combinatorial explosion" . The validity and reliability of the proposed algorithms are verified by numerical examples and engineering applications, which could be used in satellite module, multiple spindle box, rotating structure and so on.展开更多
文摘In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.
文摘In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s pheromone trails and reinforcing trails at best paths until eventually a single path is followed. On the other hand, RFD is based on copy- ing how drops form rivers by eroding the ground and de- positing sediments. In a rough sense, RFD can be seen as a gradient-oriented version of ACt. Several previous experi- ments have shown that the gradient orientation of RFD makes this method solve problems in a different way as ACt. In particular, RFD typically performs deeper searches, which in turn makes it find worse solutions than ACt in the first exe- cution steps in general, though RFD solutions surpass ACt solutions after some more time passes. In this paper we try to get the best features of both worlds by hybridizing RFD and ACt. We use a kind of ant-drop hybrid and consider both pheromone trails and altitudes in the environment. We apply the hybrid method, as well as ACt and RFD, to solve two NP-hard problems where ACt and RFD fit in a different manner： the traveling salesman problem （TSP） and the prob- lem of the minimum distances tree in a variable-cost graph （MDV）. We compare the results of each method and we an- alyze the advantages of using the hybrid approach in each case.
文摘This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP-hard problem can be converted into concave maximization dual problems without duality gap. And the dual problems can be solved, under certain conditions, by polynomial algorithms.
基金supported by the Deutsche Forschungsgemeinschaft, project PAWS (NI 369/10)supported by the Studienstiftung des Deutschen Volkes+2 种基金supported by DFG "Cluster of Excellence Multimodal Computing and Interaction"supported by DIAMANT (a mathematics cluster of the Netherlands Organization for Scientific Research NWO)the Alexander von Humboldt Foundation, Bonn, Germany
文摘Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.
基金Project supported by the National Natural Science Foundation of China.
文摘The layout optimization for the dishes installed on a rotating table is investigated. This is a packing problem with equilibrium behavioural constraints. To deal with its layout topo-models and initial layout, a mathematical model and heuristic approaches, including the method of model-changing iteration (MCI) and the method of main objects topo-models (MOT), are proposed, with a series of intuitive algorithms embedded in, such as the technique for the search under the initial guess and the strategies for remission of "combinatorial explosion" . The validity and reliability of the proposed algorithms are verified by numerical examples and engineering applications, which could be used in satellite module, multiple spindle box, rotating structure and so on.
