检索结果-内蒙古大学图书馆

The compact genetic algorithm Struggles on Cliff Functions

algorithmICA 2025年第4期87卷 507-536页

作者： Neumann, Frank Sudholt, Dirk Witt, Carsten Univ Adelaide Sch Comp & Math Sci Optimisat & Logist Adelaide SA 5005 Australia Univ Passau Fac Comp Sci & Math D-94032 Passau Germany Tech Univ Delnmark DTU Compute DK-2800 Lyngby Denmark

Estimation of distribution algorithms (EDAs) are general-purpose optimizers that maintain a probability distribution over a given search space. This probability distribution is updated through sampling from the distribution and a reinforcement learning process which rewards solution components that have shown to be part of good quality samples. The compact genetic algorithm (cGA) is a non-elitist EDA able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. We investigate the cGA on the Cliff function for which it was shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the Cliff function and investigate its dynamics both experimentally and theoretically. Our experimental results indicate that the cGA requires exponential time for all values of the update strength 1/K. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for K where the expected optimization time drops from n Theta(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n<^>{\Theta (n)}$$\end{document} to 2 Theta(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2<^>{\Theta (n)}$$\end{document}.

关键词： Estimation-of-distribution algorithms compact genetic algorithm Evolutionary algorithms Running time analysis Theory

来源：评论

学校读者我要写书评

暂无评论

compact genetic algorithm-Based Feature Selection for Sequence-Based Prediction of Dengue-Human Protein Interactions

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2022年第4期19卷 2137-2148页

作者： Dey, Lopamudra Mukhopadhyay, Anirban Heritage Inst Technol Dept Comp Sci & Engn Kolkata 700107 India Univ Kalyani Dept Comp Sci & Engn Kalyani 741235 W Bengal India

Dengue Virus (DENV) infection is one of the rapidly spreading mosquito-borne viral infections in humans. Every year, around 50 million people get affected by DENV infection, resulting in 20,000 deaths. Despite the recent experiments focusing on dengue infection to understand its functionality in the human body, several functionally important DENV-human protein-protein interactions (PPIs) have remained unrecognized. This article presents a model for predicting new DENV-human PPIs by combining different sequence-based features of human and dengue proteins like the amino acid composition, dipeptide composition, conjoint triad, pseudo amino acid composition, and pairwise sequence similarity between dengue and human proteins. A Learning vector quantization (LVQ)-based compact genetic algorithm (CGA) model is proposed for feature subset selection. CGA is a probabilistic technique that simulates the behavior of a genetic algorithm (GA) with lesser memory and time requirements. Prediction of DENV-human PPIs is performed by the weighted Random Forest (RF) technique as it is found to perform better than other classifiers. We have predicted 1013 PPIs between 335 human proteins and 10 dengue proteins. All predicted interactions are validated by literature filtering, GO-based assessment, and KEGG Pathway enrichment analysis. This study will encourage the identification of potential targets for more effective anti-dengue drug discovery.

关键词： Proteins Amino acids Viruses (medical) Feature extraction Prediction algorithms Databases genetic algorithms Dengue virus (DENV) DENV-human protein-protein interaction sequence-based prediction LVQ compact genetic algorithm feature selection

来源：评论

学校读者我要写书评

暂无评论

The Complex Parameter Landscape of the compact genetic algorithm

引用

algorithmICA 2021年第4期83卷 1096-1137页

作者： Lengler, Johannes Sudholt, Dirk Witt, Carsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Univ Sheffield Sheffield S1 4DP S Yorkshire England Tech Univ Denmark DTU Compute Lyngby Denmark

The compact genetic algorithm (cGA) evolves a probability distribution favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We study the intricate dynamics of the cGA on the test function OneMax, and how its performance depends on the hypothetical population size K, which determines how quickly decisions about promising bit values are fixated in the probabilistic model. It is known that the cGA and the Univariate Marginal Distribution algorithm (UMDA), a related algorithm whose population size is called lambda, run in expected time O(nlogn) when the population size is just large enough (K=Theta(nlogn) and lambda=Theta(nlogn) , respectively) to avoid wrong decisions being fixated. The UMDA also shows the same performance in a very different regime (lambda=Theta(logn), equivalent to K=Theta(logn) in the cGA) with much smaller population size, but for very different reasons: many wrong decisions are fixated initially, but then reverted efficiently. If the population size is even smaller (o(logn)), the time is exponential. We show that population sizes in between the two optimal regimes are worse as they yield larger runtimes: we prove a lower bound of omega(K1/3n+nlogn) for the cGA on OneMax for K=O(n/log2n). For K=omega(log3n) the runtime increases with growing K before dropping again to O(Kn+nlogn) for K=omega(nlogn) . This suggests that the expected runtime for the cGA is a bimodal function in K with two very different optimal regions and worse performance in between.

关键词： Estimation-of-distribution algorithms compact genetic algorithm Evolutionary algorithms Runtime analysis Theory

来源：评论

学校读者我要写书评

暂无评论

Integrating Heterogeneous Ontologies in Asian Languages Through compact genetic algorithm with Annealing Re-sample Inheritance Mechanism

引用

ACM TRANSACTIONS ON ASIAN AND LOW-RESOURCE LANGUAGE INFORMATION PROCESSING 2023年第3期22卷 1-21页

作者： Xue, Xingsi Liu, Wenyu Fujian Univ Technol Fujian Prov Key Lab Big Data Min & Applicat 33 Xuefu South Rd Fuzhou Fujian Peoples R China Fujian Univ Technol Sch Comp Sci & Math 33 Xuefu South Rd Fuzhou Fujian Peoples R China

An ontology is a state-of-the-art knowledge modeling technique in the natural language domain, which has been widely used to overcome the linguistic barriers in Asian and European countries' intelligent applications. However, due to the different knowledge backgrounds of ontology developers, the entities in the ontologies could be defined in different ways, which hamper the communications among the intelligent applications built on them. How to find the semantic relationships among the entities that are lexicalized in different languages is called the Cross-lingual Ontology Matching problem (COM), which is a challenge problem in the ontology matching domain. To face this challenge, being inspired by the success of the genetic algorithm (GA) in the ontology matching domain, this work proposes a compact GA with Annealing Re-sample Inheritance mechanism (CGA-ARI) to efficiently address theCOMproblem. In particular, a Cross-lingual Similarity Metric (CSM) is presented to distinguish two cross-lingual entities, a discrete optimal model is built to define the COM problem, and the compact encoding mechanism and the Annealing Re-sample Inheritance mechanism (ARI) are introduced to improve CGA's searching performance. The experiment uses Multifarm track to test CGA-ARI's performance, which includes 45 ontology pairs in different languages. The experimental results show that CGA-ARI is able to significantly improve the performance of GA and CGA and determine better alignments than state-of-the-art ontology matching systems.

关键词： Cross-lingual ontology alignment compact genetic algorithm Annealing Re-sample Inheritance Mechanism

来源：评论

学校读者我要写书评

暂无评论

TEMPLATE MATCHING IN DIGITAL IMAGES USING A compact genetic algorithm WITH ELITISM AND MUTATION

引用

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS 2010年第1期19卷 91-106页

作者： Da Silva, Rafael R. Limay, Carlos R. Erig Lopesz, Heitor S. Univ Tecnol Fed Parana Bioinformat Lab BR-80230901 Curitiba Parana Brazil

The emCGA is a new extension of the compact genetic algorithm (CGA) that includes elitism and a mutation operator. These improvements do not increase significantly the computational cost or the memory consumption and, on the other hand, increase the overall performance in comparison with other similar works. The emCGA is applied to the problem of object recognition in digital images. The objective is to find a reference image (template) in a landscape image, subject to distortions and degradation in quality. Two models for dealing with the images are proposed, both based on the intensity of light. Several experiments were done with reference and landscape images, under different situations. The emCGA was compared with an exhaustive search algorithm and another CGA proposed in the literature. The emCGA was found to be more efficient for this problem, when compared with the other algorithms. We also compared the two proposed models for the object. One of them is more suitable for images with rich details, and the other for images with low illumination level. Both models seem to perform equally in the presence of distortions. Overall, results suggested the efficiency of emCGA for template matching in images and encourages future developments.

关键词： compact genetic algorithm template matching image processing

来源：评论

学校读者我要写书评

暂无评论

DYNAMIC RELOCATION OF PLANT/WAREHOUSE FACILITIES: A FAST compact genetic algorithm APPROACH

引用

Chinese Journal of Mechanical Engineering 2004年第1期17卷 51-54页

作者： LiShugang WuZhiming PangXiaohong DepartmentofAutomation ShanghaiJiaotongUniversityShanghai200030China

The problem of dynamic relocation and phase-out of combined manufacturingplant and warehousing facilities in the supply chain are concerned. A multiple time/multipleobjective model is proposed to maximize total profit during the time horizon, minimize total accesstime from the plant/warehouse facilities to its suppliers and customers and maximize aggregatedlocal incentives during the time horizon. The relocation problem keeps the feature of NP-hard andwith the traditional method the optimal result cannot be got easily. So a compact genetic algorithm(CGA) is introduced to solve the problem. In order to accelerate the convergence speed of the CGA,the least square approach is introduced and a fast compact genetic algorithm (fCGA) is ***, simulation results with the fCGA are compared with the CGA and classical integerprogramming (IP). The results show that the fCGA proposed is of high efficiency for Paretooptimality problem.

关键词： Multiple objectives compact genetic algorithm Supply chain Least squareapproach Relocation

来源：评论

学校读者我要写书评

暂无评论

Modified compact genetic algorithm for Thinned Array Synthesis

引用

IEEE ANTENNAS AND WIRELESS PROPAGATION LETTERS 2016年 15卷 1105-1108页

作者： Ha, B. V. Mussetta, M. Pirinoli, P. Zich, R. E. Catholic Univ Louvain ICTEAM B-1348 Louvain La Neuve Belgium Politecn Milan Dipartimento Energia I-20156 Milan Italy Politecn Torino Dipartimento Elettron & Telecomunicaz I-10129 Turin Italy

In this letter, a new optimization algorithm, the Modified compact genetic algorithm (M-cGA) is introduced and applied to the synthesis of thinned arrays. The M-cGA has been derived from the compact genetic algorithm (cGA), properly modified and improved by implementing more than one probability vector (PV) and adding suitable learning scheme between these PVs. The so-obtained algorithm has been applied to the optimized synthesis of different-size linear and planar thinned arrays: In all the considered cases, it outperforms not only the cGA, but also the other optimization schemes previously applied to this kind of problem, both in terms of goodness of the solution (minimization of the peak sidelobe level) and of computational cost.

关键词： Antenna compact genetic algorithm optimization algorithm thinned array

来源：评论

学校读者我要写书评

暂无评论

A compact genetic algorithm for the network coding based resource minimization problem

引用

APPLIED INTELLIGENCE 2012年第4期36卷 809-823页

作者： Xing, Huanlai Qu, Rong Univ Nottingham Sch Comp Sci Automated Scheduling Optimisat & Planning ASAP Gr Nottingham NG8 1BB England

In network coding based data transmission, intermediate nodes in the network are allowed to perform mathematical operations to recombine (code) data packets received from different incoming links. Such coding operations incur additional computational overhead and consume public resources such as buffering and computational resource within the network. Therefore, the amount of coding operations is expected to be minimized so that more public resources are left for other network applications. In this paper, we investigate the newly emerged problem of minimizing the amount of coding operations required in network coding based multicast. To this end, we develop the first elitism-based compact genetic algorithm (cGA) to the problem concerned, with three extensions to improve the algorithm performance. First, we make use of an all-one vector to guide the probability vector (PV) in cGA towards feasible individuals. Second, we embed a PV restart scheme into the cGA where the PV is reset to a previously recorded value when no improvement can be obtained within a given number of consecutive generations. Third, we design a problem-specific local search operator that improves each feasible solution obtained by the cGA. Experimental results demonstrate that all the adopted improvement schemes contribute to an enhanced performance of our cGA. In addition, the proposed cGA is superior to some existing evolutionary algorithms in terms of both exploration and exploitation simultaneously in reduced computational time.

关键词： compact genetic algorithm Estimation of distribution algorithm Multicast Network coding

来源：评论

学校读者我要写书评

暂无评论

Constrained Mixed Integer Programming Solver Based on the compact genetic algorithm

引用

IEEE LATIN AMERICA TRANSACTIONS 2018年第5期16卷 1493-1498页

作者： Palhares, P. H. S. Brito, L. C. Univ Fed Goias Goiania Go Brazil Univ Fed Goias Escola Engn Eletr & Comp EMC Goiania Go Brazil

This paper presents a solver, the PIMAGc, for optimization of constrained mixed integer programming problems based on the compact genetic algorithm (cGA). As the cGA, the PIMAGc works with binary representation of variables. As comparison criteria and to measure the algorithm's performance, the PIMAGc was compared with the MI-LXPM, an appropriate algorithm for solving mixed integer programming problems. By using an appropriate number of problems, it was found that the PIMAGc outperformed the MI-LXPM with a greater success rate and a smaller number of evaluations on the majority of the problems, with equal performance on the others.

关键词： Mixed integer programming compact genetic algorithm constrained optimization

来源：评论

学校读者我要写书评

暂无评论

A step forward in studying the compact genetic algorithm

引用

EVOLUTIONARY COMPUTATION 2006年第3期14卷 277-289页

作者： Rastegar, Reza Hariri, Arash So Illinois Univ Dept Math Carbondale IL 62901 USA Iran Telecommun Res Ctr Tehran Iran

The compact genetic algorithm (cGA) is an Estimation of Distribution algorithm that generates offspring population according to the estimated probabilistic model of the parent population instead of using traditional recombination and mutation operators. The cGA only needs a small amount of memory;therefore, it may be quite useful in memory-constrained applications. This paper introduces a theoretical framework for studying the cGA from the convergence point of view in which, we model the cGA by a Markov process and approximate its behavior using an Ordinary Differential Equation (ODE). Then, we prove that the corresponding ODE converges to local optima and stays there. Consequently, we conclude that the cGA will converge to the local optima of the function to be optimized.

关键词： compact genetic algorithm Markov process weak convergence ordinary differential equation stationary configuration stability

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：