Quantum algorithm for minimum dominating set problem with circuit design

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.

A Reference Vector-Assisted Many-Objective Optimization Algorithm with Adaptive Niche Dominance Relation

It is still a huge challenge for traditional Pareto-dominatedmany-objective optimization algorithms to solve manyobjective optimization problems because these algorithms hardly maintain the balance between convergence and diversity and can only find a group of solutions focused on a small area on the Pareto front,resulting in poor performance of those algorithms.For this reason,we propose a reference vector-assisted algorithmwith an adaptive niche dominance relation,for short MaOEA-AR.The new dominance relation forms a niche based on the angle between candidate solutions.By comparing these solutions,the solutionwith the best convergence is found to be the non-dominated solution to improve the selection pressure.In reproduction,a mutation strategy of k-bit crossover and hybrid mutation is used to generate high-quality offspring.On 23 test problems with up to 15-objective,we compared the proposed algorithm with five state-of-the-art algorithms.The experimental results verified that the proposed algorithm is competitive.

Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem

In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.

Background dominant colors extraction method based on color image quick fuzzy c-means clustering algorithm

A quick and accurate extraction of dominant colors of background images is the basis of adaptive camouflage design.This paper proposes a Color Image Quick Fuzzy C-Means(CIQFCM)clustering algorithm based on clustering spatial mapping.First,the clustering sample space was mapped from the image pixels to the quantized color space,and several methods were adopted to compress the amount of clustering samples.Then,an improved pedigree clustering algorithm was applied to obtain the initial class centers.Finally,CIQFCM clustering algorithm was used for quick extraction of dominant colors of background image.After theoretical analysis of the effect and efficiency of the CIQFCM algorithm,several experiments were carried out to discuss the selection of proper quantization intervals and to verify the effect and efficiency of the CIQFCM algorithm.The results indicated that the value of quantization intervals should be set to 4,and the proposed algorithm could improve the clustering efficiency while maintaining the clustering effect.In addition,as the image size increased from 128×128 to 1024×1024,the efficiency improvement of CIQFCM algorithm was increased from 6.44 times to 36.42 times,which demonstrated the significant advantage of CIQFCM algorithm in dominant colors extraction of large-size images.

Diversity of Pareto front: A multiobjective genetic algorithm based on dominating information

In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.

Improved non-dominated sorting genetic algorithm (NSGA)-II in multi-objective optimization studies of wind turbine blades

The non-dominated sorting genetic algorithm （NSGA） is improved with the controlled elitism and dynamic crowding distance. A novel multi-objective optimization algorithm is obtained for wind turbine blades. As an example, a 5 MW wind turbine blade design is presented by taking the maximum power coefficient and the minimum blade mass as the optimization objectives. The optimal results show that this algorithm has good performance in handling the multi-objective optimization of wind turbines, and it gives a Pareto-optimal solution set rather than the optimum solutions to the conventional multi objective optimization problems. The wind turbine blade optimization method presented in this paper provides a new and general algorithm for the multi-objective optimization of wind turbines.

GREEDY NON-DOMINATED SORTING IN GENETIC ALGORITHM-ⅡFOR VEHICLE ROUTING PROBLEM IN DISTRIBUTION

Vehicle routing problem in distribution （VRPD） is a widely used type of vehicle routing problem （VRP）, which has been proved as NP-Hard, and it is usually modeled as single objective optimization problem when modeling. For multi-objective optimization model, most researches consider two objectives. A multi-objective mathematical model for VRP is proposed, which considers the number of vehicles used, the length of route and the time arrived at each client. Genetic algorithm is one of the most widely used algorithms to solve VRP. As a type of genetic algorithm （GA）, non-dominated sorting in genetic algorithm-Ⅱ （NSGA-Ⅱ） also suffers from premature convergence and enclosure competition. In order to avoid these kinds of shortage, a greedy NSGA-Ⅱ （GNSGA-Ⅱ） is proposed for VRP problem. Greedy algorithm is implemented in generating the initial population, cross-over and mutation. All these procedures ensure that NSGA-Ⅱ is prevented from premature convergence and refine the performance of NSGA-Ⅱ at each step. In the distribution problem of a distribution center in Michigan, US, the GNSGA-Ⅱ is compared with NSGA-Ⅱ. As a result, the GNSGA-Ⅱ is the most efficient one and can get the most optimized solution to VRP problem. Also, in GNSGA-Ⅱ, premature convergence is better avoided and search efficiency has been improved sharply.

A Modified Pareto Dominance Based Real-Coded Genetic Algorithm for Groundwater Management Model

This study proposes a groundwater management model in which the solution is performed through a combined simulation-optimization model. In the proposed model, a modular three-dimensional finite difference groundwater flow model, MODFLOW is used as simulation model. This model is then integrated with an optimization model, in which a modified Pareto dominance based Real-Coded Genetic Algorithm (mPRCGA) is adopted. The performance of the proposed mPRCGA based management model is tested on a hypothetical numerical example. The results indicate that the proposed mPRCGA based management model is an effective way to obtain good optimum management strategy and may be used to solve other type of groundwater simulation-optimization problems.

A Game Theoretic Approach for a Minimal Secure Dominating Set

The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.

Modeling and Optimization of Electrical Discharge Machining of SiC Parameters, Using Neural Network and Non-Dominating Sorting Genetic Algorithm (NSGA II)

Silicon Carbide (SiC) machining by traditional methods with regards to its high hardness is not possible. Electro Discharge Machining, among non-traditional machining methods, is used for machining of SiC. The present work is aimed to optimize the surface roughness and material removal rate of electro discharge machining of SiC parameters simultaneously. As the output parameters are conflicting in nature, so there is no single combination of machining parameters, which provides the best machining performance. Artificial neural network (ANN) with back propagation algorithm is used to model the process. A multi-objective optimization method, non-dominating sorting genetic algorithm-II is used to optimize the process. Affects of three important input parameters of process viz., discharge current, pulse on time (Ton), pulse off time (Toff) on electric discharge machining of SiC are considered. Experiments have been conducted over a wide range of considered input parameters for training and verification of the model. Testing results demonstrate that the model is suitable for predicting the response parameters. A pareto-optimal set has been predicted in this work.

论政策共识构建中的算法支配:模式与维度

人类社会进入算法时代,政策共识构建无论是在科学化发展还是在民主化进程中都受到算法影响,当这种影响发展到一定程度时则会出现算法支配的现象。根据算法的自动化程度与相对于人类的独立性,政策共识构建中的算法支配可分为四种模式:工具性支配、平台式支配、博弈性支配、自动化支配。四种模式对政策共识构建的影响体现在不同层面,但都是从四个方面展开:通过代码设计对政策诉求进行标准化解读;对个体感知做出隐蔽控制以此编辑诉求内容;形成严密的审查体系对行为进行监控并做出引导;设定计算规则塑造共识构建的程序和方式。总体而言,政策共识构建的算法支配体现为技术支配与权力支配的混合,需要基于对算法的全面认知做出应对。

领导者引导与支配解进化的多目标矮猫鼬算法

面对现实中日益复杂的多目标优化问题,需要发展新型多目标优化算法应对挑战。提出一种基于领导者引导与支配解动态缩减进化的多目标矮猫鼬优化算法(MODMO)。领导者引导机制通过引入动态权衡因子以调控侦察猫鼬探寻土丘的搜索半径,同时以非劣解集构建外部存档并根据非支配排序层级确定出领导者,进而引导侦察猫鼬向多目标前沿面推进以改善算法的收敛性;支配解动态缩减进化策略是为克服非劣解外部存档维护过程中的解冗余问题而构建,其以支配关系和拥挤距离动态筛选支配解并存入外部存档,以支配解信息融入种群进化实现多目标潜在前沿的挖掘并增强算法的多样性。在ZDT、DTLZ与WFG基准函数上,与5种代表性比较算法的实验结果表明MODMO算法在收敛性与多样性上均具有显著优势。

基于多目标狼群算法的机场行李导入系统仿真优化研究

针对民航机场行李导入系统运行过程中旅客行李注入等待时间长、系统能耗高等问题,综合考虑虚拟视窗控制方式、收集带式输送机运行速度、虚拟视窗长度及同时开放值机柜台数量等关键控制参数对机场行李导入系统运行效率的影响,提出一种求解该问题的仿真优化框架。通过分析机场行李导入系统实际运行工况,建立参数化仿真优化模型。以最小化旅客行李注入平均等待时间和系统能耗为优化目标,结合系统设计和运行过程中的实际约束条件,建立该问题的数学模型,并设计了一种多目标自适应并行狼群算法进行求解。该算法针对所提问题特性及经典狼群算法易陷入局部最优和收敛速度慢等不足,提出一种混合整实数单链编码方式,融合反向学习策略生成初始种群,引入自适应游走概率机制和智能行为并行机制,采用局部和全局自适应邻域搜索及启发式保优策略实现狼群算法智能行为搜索,使用Pareto非支配排序进行寻优迭代并获得最优解集。以国内某大型国际航空枢纽机场行李导入系统为例设计不同规模多种算法对比实验,验证了所提方法的有效性和优越性。

基于改进NSGA-Ⅱ的多目标车间物料配送方法

针对车间物料配送效率低的问题,建立以配送路径最短和时间窗惩罚值最小为目标的物料配送多目标优化模型,提出基于快速非支配排序遗传算法(NSGA-Ⅱ)的混合优化算法INSGA-Ⅱ.该算法采用密度峰值聚类(DPC)初始化种群,缩减问题规模;在NSGA-Ⅱ遗传操作阶段,采用差分进化(DE)算法,避免陷入局部最优;通过变异向量的差分操作与部分映射交叉加快迭代速度,同时提高种群多样性.通过求解不同基准函数与不同规模算例验证算法的有效性,结果表明,与传统NSGA-Ⅱ算法相比,改进算法具有更优帕累托前沿,同时算法结果的均匀性和多样性更好,求解时间更短.研究结果表明,新算法生成的结果更优;相比NSGA-Ⅱ算法、多目标粒子群算法(MOPSO),生成的总配送距离减少26.65%,总时间窗惩罚减少32.5%,能有效提高车间物料的配送效率.

基于CatBoost-NSGA-Ⅲ算法的盾构姿态预测与优化

为解决盾构掘进过程中因盾构前倾变形、蛇形、轴线偏离及纠偏等影响施工安全性与高效性的问题,提出一种将类别型特征梯度提升(CatBoost)与第三代非支配排序遗传算法(NSGA-Ⅲ)相结合的盾构姿态多目标优化方法;以贵阳地铁为例,选取22个影响因素作为输入参数,利用CatBoost算法建立输入参数与盾构姿态之间的非线性映射函数关系,采用随机森林(RF)算法评价输入参数的重要性;以盾构姿态绝对值最小化为目标,构建CatBoost-NSGA-Ⅲ多目标优化模型,并通过案例分析验证所提方法的适用性和有效性。结果表明:采用CatBoost算法训练工程实测数据得到的预测模型具有较高的精度,5个盾构姿态目标的R^(2)范围为0.916~0.943;所研发的CatBoost-NSGA-Ⅲ盾构姿态多目标优化方法,可使盾构姿态得到显著优化,整体改进的平均值为53.34%。

配电网多目标优化重构模型及多目标烟花求解算法研究

针对配电网优化重构问题,以最小化有功网损、最小化电压偏移度以及最小化负荷平衡度作为目标函数建立配电网多目标优化重构模型。提出一种多策略混合的改进烟花算法(Improved fireworks algorithm,IMFWA)进行求解。算法采用不重复环路编码,压缩解空间,提高搜索效率;采用Sobol序列生成初始种群,增强种群的多样性和遍历性;利用优化烟花和随机烟花进行位移操作,保持种群多样性;采用高斯与柯西的混合变异方式,提高寻优效率;利用Pareto支配关系以及适应度与拥挤度函数组成的综合指标对最优解集进行排列选取,提高收敛速度。对IEEE-33节点系统进行仿真试验,验证了所提出的方法是有效和可行的,试验结果表明优化重构方案能够有效改善配电网的运行指标,并根据不同实际情况为电网人员提供重构方案。

提升光储充电站运行效率的多目标优化配置策略

光储充电站的运行效率直接影响到其经济效益及电网侧的电能质量。针对在进行容量配置时对运行效率考虑不足会导致非必要的电能损耗,文中提出一种提升光储充电站运行效率的多目标优化配置策略。通过分析光储充电站变换器与内源线路功率损耗对于运行效率的影响,提出充电站的运行效率评估指标与计算方法,并讨论光储充电站运行效率对其容量配置的影响。建立以充电站经济效益、运行效率、电网侧峰谷供电功率补偿能力最佳为优化目标的多目标容量优化配置策略。针对优化目标特性,提出一种改进二代非支配排序遗传算法得到优化策略求解方法。选取中国西南地区某典型光储充电站运营场景,通过算例验证了优化策略的有效性与优越性。

基于NSGA-Ⅱ的滑油泵叶轮结构优化设计

滑油泵常需要在高空、低压工况下稳定运转,常会出现供油不足、效率降低等问题。为了得到满足设计要求且具有最佳性能的滑油泵,以某直升机用滑油泵叶轮为研究对象,对其结构进行优化设计。选择高空两个典型工况的效率与扬程作为优化目标,利用NSGA-Ⅱ算法对滑油泵叶轮几何参数进行寻优,对优化前后的滑油泵效率、扬程进行对比分析。采用CFD流体仿真及实验方法对优化结果进行对比验证。结果表明:所选优化参数对滑油泵性能有较大影响,优化后的滑油泵叶片位置附近流动更加平稳,高低压区域过渡平缓,能量损失更小,且降低了汽蚀发生的可能性;优化后的滑油泵设计点扬程提高2.6 m,效率提高2.86%。

平行行为的反垄断规制

长期以来,传统寡头市场中大企业协调一致的平行行为的反垄断规制一直困难重重,也由此产生了一系列相互交错的制度工具。这些制度工具包含多种相互关联的基本概念,也反映了反垄断规制对于平行行为的复杂的理论立场。随着算法时代的来临,反垄断法将面对数量更多、更为稳固的平行行为。必须进一步将缺乏合意证据的“协议”、滥用共同支配地位行为、算法合谋等视为一个同源的整体——平行行为,并明确反垄断法相应的制度工具及其发展变化,才能更好地实现对平行行为的规制。

磁链闭环控制下接触器的优化设计方法

该文对接触器的优化设计进行研究,将磁链闭环控制引入接触器本体优化设计中,实现控制策略与本体优化设计的协同。首先,综合考虑接触器的外部漏磁和磁场分布特性,在三维有限元动态仿真的基础上构建改进的磁路模型,以实现磁路模型的参数化计算。然后,提出了一种改进的非支配排序遗传算法(NSGA-Ⅱ)与磁路模型相结合进行优化设计,以Pareto前沿个数判断种群进化进程,实现自适应遗传-差分混合进化策略,提高了多目标优化设计算法的全局收敛性和收敛速度。最后,将恒磁链闭环控制策略与多目标优化设计相结合,通过减小接触器的电磁惯性、机械惯性及提高控制磁通密度,来提高机构响应速度和磁性材料利用率,同时减小触头弹跳。仿真及实验验证了改进磁路模型及多目标优化设计方法的有效性。