Hybrid Discrete Particle Swarm Optimization Algorithm for Control Pattern Assignment

ZENG Yu-qin; CAI Hua-yang; ZHOU Ru-ping; LIU Geng-geng; HUANG Xing; XU Ning

doi:10.12263/DZXB.20221166

您当前的位置：

首页 >

文章列表页 >

Hybrid Discrete Particle Swarm Optimization Algorithm for Control Pattern Assignment

PAPERS | 更新时间：2025-12-08

- Hybrid Discrete Particle Swarm Optimization Algorithm for Control Pattern Assignment
- ACTA ELECTRONICA SINICA Vol. 52, Issue 8, Pages: 2836-2849(2024)
- 作者机构：
  
  1.福州大学计算机与大数据学院,福建福州 350108
  2.西北工业大学计算机学院,陕西西安 710072
  3.武汉理工大学信息工程学院,湖北武汉 430070
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61877010)
- DOI：10.12263/DZXB.20221166
  CLC： TP391;
- Received：14 October 2022，
  
  Revised：2022-12-07，
  
  Published：25 August 2024
- 稿件说明：
移动端阅览
曾裕钦, 蔡华洋, 周茹平, 等. 基于混合离散粒子群优化的控制模式分配算法[J]. 电子学报, 2024, 52(08): 2836-2849.

ZENG Yu-qin, CAI Hua-yang, ZHOU Ru-ping, et al. Hybrid Discrete Particle Swarm Optimization Algorithm for Control Pattern Assignment[J]. Acta Electronica Sinica, 2024, 52(08): 2836-2849.
曾裕钦, 蔡华洋, 周茹平, 等. 基于混合离散粒子群优化的控制模式分配算法[J]. 电子学报, 2024, 52(08): 2836-2849. DOI：10.12263/DZXB.20221166

ZENG Yu-qin, CAI Hua-yang, ZHOU Ru-ping, et al. Hybrid Discrete Particle Swarm Optimization Algorithm for Control Pattern Assignment[J]. Acta Electronica Sinica, 2024, 52(08): 2836-2849. DOI：10.12263/DZXB.20221166

摘要

连续微流控生物芯片是生物化学实验自动化、微型化的革命性技术.多路复用器的控制模式分配作为连续微流控生物芯片自动化设计的关键环节之一，是难的NP（Non-deterministic Polynomial）优化问题.现有工作采用粒子群优化算法求解控制模式分配问题存在过早陷入局部最优解、收敛速度慢以及算法稳定性差的缺点.为此，本文提出一种连续微流控生物芯片下基于混合离散粒子群优化的控制模式分配算法.首先，为了加快算法收敛速度及避免过早陷入局部最优解，提出了离散的自适应区域搜索策略.其次，通过基于样例的社会学习机制提高了算法的稳定性.然后，采用等距抽值的方式筛选出自适应区域搜索策略中重要参数的最佳组合，以进一步提高分配方案的质量.最终实验结果表明，所提算法在多路复用器中阀门使用数量上平均优化了19.01%，在算法稳定性上提高了29.18%，且在现实的生化应用中有良好的性能表现.

Abstract

Continuous-flow microfluidic biochip is a revolutionary technology for automation and miniaturization of biochemical experiments. As one of the key links in the automatic design of continuous microfluidic biochips

the control pattern assignment problem of multiplexers is an NP-hard combinatorial optimization problem. The existing particle swarm optimization algorithm for control pattern assignment problem has the disadvantages of falling into local optimal solution prematurely

slow convergence speed

and poor stability of the algorithm. In this paper

control pattern assignment algorithm based on hybrid discrete particle swarm optimization for continuous-flow microfluidic biochips is proposed. First

in order to accelerate the convergence speed of the proposed algorithm and avoid falling into a local optimum prematurely

a discrete adaptive region search strategy is proposed. Second

the stability of the proposed algorithm is improved by a sample-based social learning mechanism. Third

the optimal combination of the important parameters in the adaptive region search strategy is selected by equidistant sampling to further improve the results. The final experimental results show that the proposed algorithm optimizes the number of valves by an average of 19.01%

and improves the stability of the algorithm by 29.18%

and then performs well in practical biochemical applications.

关键词

Keywords

references

BALAGADDÉ F K , YOU L , HANSEN C L , et al . Long-term monitoring of bacteria undergoing programmed population control in a microchemostat [J ] . Science , 2005 , 309 ( 5731 ): 137 - 140 .

WHITESIDES G M . The origins and the future of microfluidics [J ] . Nature , 2006 , 442 ( 7101 ): 368 - 373 .

YAGER P , EDWARDS T , FU E , et al . Microfluidic diagnostic technologies for global public health [J ] . Nature , 2006 , 442 ( 7101 ): 412 - 418 .

UNGER M A , CHOU H P , THORSEN T , et al . Monolithic microfabricated valves and pumps by multilayer soft lithography [J ] . Science , 2000 , 288 ( 5463 ): 113 - 116 .

ROGERS J A , NUZZO R G . Recent progress in soft lithography [J ] . Materials Today , 2005 , 8 ( 2 ): 50 - 56 .

YAO H , HO T Y , CAI Y . PACOR: Practical control-layer routing flow with length-matching constraint for flow-based microfluidic biochips [C ] // ACM/EDAC/IEEE Design Automation Conference . Piscataway : IEEE , 2015 : 1 - 6 .

HU K , DINH T A , HO T Y , et al . Control-layer routing and control-pin minimization for flow-based microfluidic biochips [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2016 , 36 ( 1 ): 55 - 68 .

HONG J W , QUAKE S R . Integrated nanoliter systems [J ] . Nature Biotechnology , 2003 , 21 ( 10 ): 1179 - 1183 .

THORSEN T , MAERKL S J , QUAKE S R . Microfluidic large-scale integration [J ] . Science , 2002 , 298 ( 5593 ): 580 - 584 .

GROVER W H , IVESTER R H C , JENSEN E C , et al . Development and multiplexed control of latching pneumatic valves using microfluidic logical structures [J ] . Lab on a Chip , 2006 , 6 ( 5 ): 623 - 631 .

KIM S J , LAI D , PARK J Y , et al . Microfluidic automation using elastomeric valves and droplets: Reducing reliance on ex-ternal controllers [J ] . Small , 2012 , 8 ( 19 ): 2925 - 2934 .

ZHONG J F , CHEN Y , MARCUS J S , et al . A microfluidic processor for gene expression profiling of single human embryonic stem cells [J ] . Lab on a Chip , 2008 , 8 ( 1 ): 68 - 74 .

WANG Q , XU Y , ZUO S , et al . Pressure-aware control layer optimization for flow-based microfluidic biochips [J ] . IEEE Transactions on Biomedical Circuits and Systems , 2017 , 11 ( 6 ): 1488 - 1499 .

ZHU Y , HUANG X , LI B , et al . Multicontrol: Advanced control-logic synthesis for flow-based microfluidic biochips [J ] . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2019 , 39 ( 10 ): 2489 - 2502 .

POLI R , KENNEDY J , BLACKWELL T . Particle swarm optimization [J ] . Swarm Intelligence , 2007 , 1 ( 1 ): 33 - 57 .

GONG Y J , ZHANG J , CHUNG H S H , et al . An efficient resource allocation scheme using particle swarm optimization [J ] . IEEE Transactions on Evolutionary Computation , 2012 , 16 ( 6 ): 801 - 816 .

LIU G , CHEN Z , ZHUANG Z , et al . A unified algorithm based on HTS and self-adapting PSO for the construction of octagonal and rectilinear SMT [J ] . Soft Computing , 2020 , 24 ( 6 ): 3943 - 3961 .

SU B , LIN Y , WANG J , et al . Sewage treatment system for improving energy efficiency based on particle swarm optimization algorithm [J ] . Energy Reports , 2022 , 8 : 8701 - 8708 .

SETAYESH M , ZHANG M , JOHNSTON M . A novel particle swarm optimisation approach to detecting continuous, thin and smooth edges in noisy images [J ] . Information Sciences , 2013 , 246 : 28 - 51 .

CEYLAN Z . Short-term prediction of COVID-19 spread using grey rolling model optimized by particle swarm optimization [J ] . Applied Soft Computing , 2021 , 109 : 107592 .

CHEN X , LIU G , XIONG N , et al . A survey of swarm intelligence techniques in VLSI routing problems [J ] . IEEE Access , 2020 , 8 : 26266 - 26292 .

朱予涵 , 黄鸿斌 , 林泓星 , 等 . 连续微流控生物芯片下基于序列对的流层物理设计算法 [J ] . 计算机辅助设计与图形学学报 , 2022 , 34 ( 4 ): 535 - 544 .

ZHU Y H , HUANG H B , LIN H X , et al . Sequence-pair-based flow-layer physical design algorithm for continuous-flow microfluidic biochips [J ] . Journal of Computer-Aided Design and Computer Graphics , 2022 , 34 ( 4 ): 535 - 544 . (in Chinese)

MOLINA D , HERRERA F . Iterative hybridization of DE with local search for the CEC’2015 special session on large scale global optimization [C ] // IEEE Congress on Evolutionary Computation . Piscataway : IEEE , 2015 : 1974 - 1978 .

LIU G , ZHOU R , XU S , et al . Two-stage competitive particle swarm optimization based timing-driven X-routing for IC design under smart manufacturing [J ] . ACM Transactions on Management Information Systems , 2022 , 13 ( 4 ): 1 - 26 .

CHENG R , JIN Y . A social learning particle swarm optimization algorithm for scalable optimization [J ] . Information Sciences , 2015 , 291 : 43 - 60 .

王毅 , 李晓梦 , 耿国华 , 等 . 基于直觉模糊熵的混合粒子群优化算法 [J ] . 电子学报 , 2021 , 49 ( 12 ): 2381 - 2389 .

WANG Y , LI X M , GENG G H , et al . Hybrid particle swarm optimization algorithm based on intuitionistic fuzzy entropy [J ] . Acta Electronica Sinica , 2021 , 49 ( 12 ): 2381 - 2389 . (in Chinese)

刘耿耿 , 黄逸飞 , 王鑫 , 等 . 基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法 [J ] . 计算机学报 , 2021 , 44 ( 12 ): 2542 - 2559 .

LIU G G , HUANG Y F , WANG X , et al . Hybrid discrete particle swarm optimization algorithm for X-architecture Steiner minimal tree construction with Slew constraints [J ] . Chinese Journal of Computers , 2021 , 44 ( 12 ): 2542 - 2559 . (in Chinese)

YU Z , SI Z , LI X , et al . A novel hybrid particle swarm optimization algorithm for path planning of UAVs [J ] . IEEE Internet of Things Journal , 2022 , 9 ( 22 ): 22547 - 22558 .

ZHAO S Z , LIANG J J , SUGANTHAN P N , et al . Dynamic multi-swarm particle swarm optimizer with local search for large scale global optimization [C ] // IEEE Congress on Evolutionary Computation . Piscataway : IEEE , 2008 : 3845 - 3852 .

JIAN J R , CHEN Z G , ZHAN Z H , et al . Region encoding helps evolutionary computation evolve faster: A new solution encoding scheme in particle swarm for large-scale optimization [J ] . IEEE Transactions on Evolutionary Computation , 2021 , 25 ( 4 ): 779 - 793 .

XUE J , SHEN B , PAN A . An intensified sparrow search algorithm for solving optimization problems [J ] . Journal of Ambient Intelligence and Humanized Computing , 2023 , 14 ( 7 ): 9173 - 9189 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Solutions of Complicated Coalition Generation Based on Discrete Particle Swarm Optimization

Estimation of Distribution-Discrete Particle Swarm Optimization Algorithm for Permutation-Based Problems

Related Author

HUANG Xing

SU Zhao-pin

XIA Na

JIANG Jian-guo

ZHANG Guo-fu

ZHOU Ya-lan

WANG Jia-hai

HUANG Cong

Related Institution

School of Computer Science, Northwestern Polytechnical University, Xian

School of Computer and Information Science,Hefei University of Technology

Engineering Research Center of Safety Critical Industrial Measurement and Control Technology,Ministry of Education

广东财经大学信息学院

中山大学计算机科学系

⁰