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 algor...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.展开更多
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2~kn^2m)的算法,其中,m为DNA...个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2~kn^2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k_1-1)k_22^(2h)+(k_1+1)^(2h)+nk_2+mk_1)的新算法,其中,k_1为一个片断覆盖的最大SNP位点数(不大于n),k_2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k_2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.展开更多
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件...二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。展开更多
基金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 No.60433020(国家自然科学基金)the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0683(新世纪优秀人才支持计划)+1 种基金the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant No.IRT0661(国家教育部创新团队资助项目)the Scientific Research Fund of Hunan Provincial Education Department of China under Grant No.06C52(湖南省教育厅资助科研项目)
文摘个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2~kn^2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k_1-1)k_22^(2h)+(k_1+1)^(2h)+nk_2+mk_1)的新算法,其中,k_1为一个片断覆盖的最大SNP位点数(不大于n),k_2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k_2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.
文摘二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。
基金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(长江学者和创新团队发展计划)
