Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton...Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.展开更多
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.展开更多
Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the tra...Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the trajectory deformation for optimization of the foot trajectory.Furthermore,the quantitative index of fitness convergence is insufficient.In this paper,we perform gait optimization of a quadruped robot using foot placement perturbation based on EC.The proposed algorithm has an atypical solution search range,which is generated by independent manipulation of each placement that forms the foot trajectory.A convergence index is also introduced to prevent premature cessation of learning.The conventional algorithm and the proposed algorithm are applied to a quadruped robot;walking performances are then compared by gait simulation.Although the two algorithms exhibit similar computation rates,the proposed algorithm shows better fitness and a wider search range.The evolutionary tendency of the walking trajectory is analyzed using the optimized results,and the findings provide insight into reliable leg trajectory design.展开更多
The search efficiency of differential evolution (DE) algorithm is greatly impacted by its control parameters. Although many adaptation/self-adaptation techniques can automatically find suitable control parameters fo...The search efficiency of differential evolution (DE) algorithm is greatly impacted by its control parameters. Although many adaptation/self-adaptation techniques can automatically find suitable control parameters for the DE, most techniques are based on pop- ulation information which may be misleading in solving complex optimization problems. Therefore, a self-adaptive DE (i.e., JADE) using two-phase parameter control scheme (TPC-JADE) is proposed to enhance the performance of DE in the current study. In the TPC-JADE, an adaptation technique is utilized to generate the control parameters in the early population evolution, and a well-known empirical guideline is used to update the control parameters in the later evolution stages. The TPC-JADE is compared with four state-of-the-art DE variants on two famous test suites (i.e., IEEE CEC2005 and IEEE CEC2015). Results indicate that the overall performance of the TPC-JADE is better than that of the other compared algorithms. In addition, the proposed algorithm is utilized to obtain optimal nutrient and inducer feeding for the Lee-Ramirez bioreactor. Experimental results show that the TPC-JADE can perform well on an actual dynamic optimization problem.展开更多
This article seeks to outline an integrated and practical geometric optimization design system(GODS)incorporating hybrid graphical electromagnetic computing-wedge modeling(GRECO-WM)scheme and the genetic algorithm(GA)...This article seeks to outline an integrated and practical geometric optimization design system(GODS)incorporating hybrid graphical electromagnetic computing-wedge modeling(GRECO-WM)scheme and the genetic algorithm(GA)for calculating the radar cross section(RCS)and optimizing the geometric parameters of a large and complex target respectively.A new wedge modeling(WM)scheme is presented for calculating the high-frequency RCS of wedge with only one visible facet based on the method of equivalent currents(MEC).The applications of GODS to 2D cross-section and 3D surface are respectively implemented by choosing an average of monostatic RCS values corresponding to a series of incident angles over a frequency band as the optimum objective function.And the results demonstrate that the RCS can be effectively and conveniently reduced by the GODS presented in this article.展开更多
Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced va...Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced variational hybrid algorithm(EVQLSE)that leverages both quantum and classical computing paradigms to address the solution of linear equation systems.Initially,an innovative loss function is proposed,drawing inspiration from the similarity measure between two quantum states.This function exhibits a substantial improvement in computational complexity when benchmarked against the variational quantum linear solver.Subsequently,a specialized parameterized quantum circuit structure is presented for small-scale linear systems,which exhibits powerful expressive capabilities.Through rigorous numerical analysis,the expressiveness of this circuit structure is quantitatively assessed using a variational quantum regression algorithm,and it obtained the best score compared to the others.Moreover,the expansion in system size is accompanied by an increase in the number of parameters,placing considerable strain on the training process for the algorithm.To address this challenge,an optimization strategy known as quantum parameter sharing is introduced,which proficiently minimizes parameter volume while adhering to exacting precision standards.Finally,EVQLSE is successfully implemented on a quantum computing platform provided by IBM for the resolution of large-scale problems characterized by a dimensionality of 220.展开更多
Evolutionary computation (EC) is one of the fastest growing areas in computer science that solves intractable optimization problems by emulating biologic evolution and organizational behaviors in nature. To de- sign...Evolutionary computation (EC) is one of the fastest growing areas in computer science that solves intractable optimization problems by emulating biologic evolution and organizational behaviors in nature. To de- sign an EC algorithm, one needs to determine a set of algorithmic configurations like operator selections and parameter settings. How to design an effective and ef- ficient adaptation scheme for adjusting the configura- tions of EC algorithms has become a significant and promising research topic in the EC research community. This paper intends to provide a comprehensive survey on this rapidly growing field. We present a classification of adaptive EC (AEC) algorithms from the perspective of how an adaptation scheme is designed, involving the adaptation objects, adaptation evidences, and adapta- tion methods. In particular, by analyzing tile popula- tion distribution characteristics of EC algorithms, we discuss why and how the evolutionary state information of EC can be estimated and utilized for designing ef- fective EC adaptation schemes. Two AEC algorithms using the idea of evolutionary state estimation, includ- ing the clustering-based adaptive genetic algorithm and the adaptive particle swarm optimization algorithm are presented in detail. Some potential directions for the re- search of AECs are also discussed in this paper.展开更多
This paper considers three algorithms for the extraction of square roots of complex integers {called Gaussians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analog...This paper considers three algorithms for the extraction of square roots of complex integers {called Gaussians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analogous algorithms extracting square roots of either real or complex integers in arithmetic based on modulus p, where is a real prime. A cryptographic system based on these algorithms is provided in this paper. A procedure reducing the computational complexity is described as well. Main results are explained in several numeric illustrations.展开更多
基金supported by the National Natural Science Foundation of China (Nos. 61173051, 61103033, and 61232001)
摘要Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.
基金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.
基金This work was supported in part by the National Research Foundation of Korea(NRF)Grant funded by the Korean Government(MSIT)(No.NRF-2019R1A2C2084677)the 2021 Research Fund(1.210052.01)of UNIST(Ulsan National Institute of Science and Technology).
摘要Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the trajectory deformation for optimization of the foot trajectory.Furthermore,the quantitative index of fitness convergence is insufficient.In this paper,we perform gait optimization of a quadruped robot using foot placement perturbation based on EC.The proposed algorithm has an atypical solution search range,which is generated by independent manipulation of each placement that forms the foot trajectory.A convergence index is also introduced to prevent premature cessation of learning.The conventional algorithm and the proposed algorithm are applied to a quadruped robot;walking performances are then compared by gait simulation.Although the two algorithms exhibit similar computation rates,the proposed algorithm shows better fitness and a wider search range.The evolutionary tendency of the walking trajectory is analyzed using the optimized results,and the findings provide insight into reliable leg trajectory design.
基金supported by National Natural Science Foundation of China(Nos.61603244 and 41505001)Fundamental Research Funds for the Central Universities(No.222201717006)
摘要The search efficiency of differential evolution (DE) algorithm is greatly impacted by its control parameters. Although many adaptation/self-adaptation techniques can automatically find suitable control parameters for the DE, most techniques are based on pop- ulation information which may be misleading in solving complex optimization problems. Therefore, a self-adaptive DE (i.e., JADE) using two-phase parameter control scheme (TPC-JADE) is proposed to enhance the performance of DE in the current study. In the TPC-JADE, an adaptation technique is utilized to generate the control parameters in the early population evolution, and a well-known empirical guideline is used to update the control parameters in the later evolution stages. The TPC-JADE is compared with four state-of-the-art DE variants on two famous test suites (i.e., IEEE CEC2005 and IEEE CEC2015). Results indicate that the overall performance of the TPC-JADE is better than that of the other compared algorithms. In addition, the proposed algorithm is utilized to obtain optimal nutrient and inducer feeding for the Lee-Ramirez bioreactor. Experimental results show that the TPC-JADE can perform well on an actual dynamic optimization problem.
基金National Natural Science Foundation of China(20095251024)
摘要This article seeks to outline an integrated and practical geometric optimization design system(GODS)incorporating hybrid graphical electromagnetic computing-wedge modeling(GRECO-WM)scheme and the genetic algorithm(GA)for calculating the radar cross section(RCS)and optimizing the geometric parameters of a large and complex target respectively.A new wedge modeling(WM)scheme is presented for calculating the high-frequency RCS of wedge with only one visible facet based on the method of equivalent currents(MEC).The applications of GODS to 2D cross-section and 3D surface are respectively implemented by choosing an average of monostatic RCS values corresponding to a series of incident angles over a frequency band as the optimum objective function.And the results demonstrate that the RCS can be effectively and conveniently reduced by the GODS presented in this article.
基金supported by the National Natural Science Foundation of China under Grant Nos.62172268 and 62302289the Shanghai Science and Technology Project under Grant Nos.21JC1402800 and 23YF1416200。
摘要Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage,widely employed in the era of noisy intermediate-scale quantum computing.This study presents an advanced variational hybrid algorithm(EVQLSE)that leverages both quantum and classical computing paradigms to address the solution of linear equation systems.Initially,an innovative loss function is proposed,drawing inspiration from the similarity measure between two quantum states.This function exhibits a substantial improvement in computational complexity when benchmarked against the variational quantum linear solver.Subsequently,a specialized parameterized quantum circuit structure is presented for small-scale linear systems,which exhibits powerful expressive capabilities.Through rigorous numerical analysis,the expressiveness of this circuit structure is quantitatively assessed using a variational quantum regression algorithm,and it obtained the best score compared to the others.Moreover,the expansion in system size is accompanied by an increase in the number of parameters,placing considerable strain on the training process for the algorithm.To address this challenge,an optimization strategy known as quantum parameter sharing is introduced,which proficiently minimizes parameter volume while adhering to exacting precision standards.Finally,EVQLSE is successfully implemented on a quantum computing platform provided by IBM for the resolution of large-scale problems characterized by a dimensionality of 220.
摘要Evolutionary computation (EC) is one of the fastest growing areas in computer science that solves intractable optimization problems by emulating biologic evolution and organizational behaviors in nature. To de- sign an EC algorithm, one needs to determine a set of algorithmic configurations like operator selections and parameter settings. How to design an effective and ef- ficient adaptation scheme for adjusting the configura- tions of EC algorithms has become a significant and promising research topic in the EC research community. This paper intends to provide a comprehensive survey on this rapidly growing field. We present a classification of adaptive EC (AEC) algorithms from the perspective of how an adaptation scheme is designed, involving the adaptation objects, adaptation evidences, and adapta- tion methods. In particular, by analyzing tile popula- tion distribution characteristics of EC algorithms, we discuss why and how the evolutionary state information of EC can be estimated and utilized for designing ef- fective EC adaptation schemes. Two AEC algorithms using the idea of evolutionary state estimation, includ- ing the clustering-based adaptive genetic algorithm and the adaptive particle swarm optimization algorithm are presented in detail. Some potential directions for the re- search of AECs are also discussed in this paper.
基金Supported by the National Natural Science Foundation of China under Grant Nos.6043302060773111(国家自然科学基金)+1 种基金the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683(新世纪优秀人才支持计划)the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No.IRT0661(长江学者和创新团队发展计划)
摘要This paper considers three algorithms for the extraction of square roots of complex integers {called Gaussians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analogous algorithms extracting square roots of either real or complex integers in arithmetic based on modulus p, where is a real prime. A cryptographic system based on these algorithms is provided in this paper. A procedure reducing the computational complexity is described as well. Main results are explained in several numeric illustrations.