Applying Autonomous Hybrid Agent-based Computing to Difficult Optimization Problems

2025-04-30 0 0 1.72MB 29 页 10玖币

侵权投诉

Applying Autonomous Hybrid Agent-based Computing

to Diﬃcult Optimization Problems

Mateusz Godzik, Jacek Dajda, Marek Kisiel-Dorohinicki, Aleksander Byrski

AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krakow, Poland,

{godzik,dajda,doroh,olekb}@agh.edu.pl

Leszek Rutkowski

Institute of Computer Science, AGH University of Science and Technology

Patryk Orzechowski, Joost Wagenaar

Department of Biostatistics, Epidemiology and Informatics, University of Pennsylvania

Jason H. Moore

Department of Computational Biomedicine at Cedars-Sinai Medical Center

Abstract

Evolutionary multi-agent systems (EMASs) are very good at dealing with diﬃcult, multi-dimensional

problems, their eﬃcacy was proven theoretically based on analysis of the relevant Markov-Chain

based model. Now the research continues on introducing autonomous hybridization into EMAS.

This paper focuses on a proposed hybrid version of the EMAS, and covers selection and introduc-

tion of a number of hybrid operators and deﬁning rules for starting the hybrid steps of the main

algorithm. Those hybrid steps leverage existing, well-known and proven to be eﬃcient metaheuris-

tics, and integrate their results into the main algorithm. The discussed modiﬁcations are evaluated

based on a number of diﬃcult continuous-optimization benchmarks.

Keywords: Agent-based computing, Hybrid metaheuristics, Nature-inspired algorithms

1. Introduction

Despite the recent increases in computer performance, not all problems can be resolved in a

timely manner. Solving problems by deterministic algorithms often takes too long (e.g., exceeding

a dozen or so of cities in the traveling salesman problem (TSP) is such an example [1]). However,

some problems do not have deterministic solutions. In these as well as in other cases, novel stochastic

Preprint submitted to Journal of L

X Templates October 25, 2022

arXiv:2210.13205v1 [cs.NE] 24 Oct 2022

methods can help. If other solutions do not meet the assumed goals, one can use metaheuristics;

their great advantage is that they do not require information about the characteristics of the search

space. One of the advantages is the ability to tune the algorithm through the selection of parameters

(cf. iRace [2]) or the ability to combine it with other algorithms to create hybrid algorithms (cf.

Talbi [3]). We are still looking for new metaheuristics, as it is impossible to ﬁnd a single method

that will solve all problems with the same accuracy (cf. Wolpert and MacReady [4]).

An example of such metaheuristics is the concept of an evolutionary multi-agent system (EMAS),

which was introduced in 1996 [5]. It is a kind of combination of the evolutionary method [6] with

the agent paradigm [7], resulting in a program in which agents are part of the computational

process that searches the admissible space. Moreover, it leverages e.g., a decentralized selection

mechanism based on a non-renewable resource and two actions: reproduction, and death. There is

no centralized control, so such algorithms can be easily implemented in a concurrent manner; this

allows for a signiﬁcant reduction in the computation time. As was proven in [8] (a formal proof

that followed the works of Michael Vose [9] showed that a Markov-chain that models the dynamics

of EMAS is ergodic, so this algorithm can reach any possible solution of a given problem), it has

become a solid base for attempts to be combined with other algorithms; this has yielded interesting

hybrid computing methods (e.g., [10]).

This grounds a hybrid evolutionary multi-agent systems (HEMAS) and discusses the selected

classic metaheuristics in detail, which have become the bases for the hybridization of EMAS. These

metaheuristics are executed during the main course of the EMAS algorithm (when certain conditions

are met). Moreover, these conditions are also discussed, and all the deliberations are illustrated

with the outcomes of experiments that are based on diﬃcult continuous optimization problems.

The main contributions, novelties, and characteristics of this paper can be summarized as follows:

•We propose a novel concept of an agent-based computing system for solving diﬃcult opti-

mization problems.

•Our proposition involves hybridizing classical EMAS systems with global optimization meta-

heuristic algorithms – particle swarm optimization (PSO), and the genetic algorithm (GA) –

leading to HEMAS systems.

•The hybridization is triggered by implementing several rules that have been proposed to design

the HEMAS systems.

•We solved the problem of redistributing the agents’ energy by using an appropriate redistri-

bution operator.

•Through extensive computer simulations, we show that the proposed HEMAS computing

system produces competitive results as compared to EMAS (the version with two hybrid

algorithms was better than the one with one hybrid algorithm, yet the version with three

hybrid algorithms was not superior to the one with two) by using proper comparison metrics

(the numbers of the evaluations of the ﬁtness functions); these are independent from the

algorithm, implementation, and hardware.

The outline of the paper is as follows. After the introduction, we describe the original EMAS

(with references to the state of the art) and follow with the description of HEMAS. Then, the details

that are related to the hybridization with the selected metaheuristics are given (the concept, and

the later parameters). Finally, the experimental setting and the results are shown and discussed,

and the paper is concluded.

2. Original EMAS

EMAS may be perceived as a “proactive” alternative to classical evolutionary computation tech-

niques that can relieve evolutionary metaheuristics of several inconsistencies with a real-life evo-

lution; e.g., a lack of global control, and asynchronous reproduction. In this system, solutions

(genotypes) are assigned to agents, realizing the several types of actions that are available to them

in order to upgrade their solutions. Agents can meet with each other and either compete or ex-

change resources. In the former case, only the richer agent is allowed to reproduce (analogical to

selection in EA); in the latter, part of the resources of the poorer agent are allocated to the richer

one (analogical to crossover in EA) [5]. For a schematic view of EMAS, one can refer to Fig. 1. It

is to note that the correctness of EMAS as a global universal optimizer has been formally proven

by using Markov chain-based models that were inspired by the theoretical works of Michael Vose

[11]. EMAS also has many extensions; e.g., an immunological one [12] that was applied to solve

diﬀerent single-criterion and multi-criteria problems.

The relationship between the elements of the algorithm is presented in Fig. 1. The agency is

based on the particular implementation that has been used in numerous projects over the last two

decades, and the agents are implemented as entities that undergo event-driven simulations [13];

Figure 1: Diagram of evolutionary multi-agent systems

ergo, the focus can be placed on the actual algorithm and not waste time on implementing the

agents as threads or processes, along with all of the necessary communication mechanisms.

The detailed EMAS algorithm is summarized in Algorithm 1. It can be noticed that the setting

is quite similar to the classic genetic algorithm, for example. This implementation method of

an agent-based computing system makes it possible to retain the idea of agency yet utilize simple

technologies (in the discussed case, the system is based on jMetal [14]). The agent-oriented activities

are actually realized inside the steps; e.g., meetStep(),reproStep(), and deadStep(). The event-driven

simulation approach consists of making it possible that each agent realizes these steps one at a time

when certain conditions are true. Thus, the concurrency is simulated, and the whole approach is

very easy to implement and port among diﬀerent metaheuristic-oriented software frameworks.

The event-driven approach allows for the building of a system that consists of loosely coupled

components that communicate by using a simple mechanism of transmitted and received events.

This architecture considerably simpliﬁes the system distribution and makes it more scalable and re-

sistant to failures. One can notice that these are expected features for each computing architecture.

It is also compatible with the agent-computing paradigm that assumes that loosely coupled inde-

pendent agents communicate with each other. The implementation of the agent paradigm in the

event-driven architecture can be easily realized by treating agents as both emitters and consumers

of the messages and can be freely conﬁgured and adopted to diﬀerent hybrids of EMAS.

Algorithm 1 EMAS algorithm pseudocode

1: function run

2: initProgress()

3: createInitialPopulation()

4: while !isStoppingConditionReached() do

5: meetStep()

6: reproStep()

7: deadStep()

8: updateProgress()

9: end while

10: end function

3. Agent-based hybrid EMAS

EMAS also has many extensions that can be used to solve diﬀerent single-criterion and multi-

criteria problems. Among others, it is worth mentioning immunological EMAS, elitist EMAS for

multi-objective optimization, CoEMAS, memetic agent-based continuous optimization, and hybrids

of EDA-type and EMAS algorithms. All of these are brieﬂy presented below.

Immunological EMAS (iEMAS) [12] assumes the introduction of a new group of agents that act

as lymphocyte T-cells (following an immunological inspiration). The goal of these special agents is

to introduce a negative-selection mechanism into the evolution process that would eliminate other

agents with similar genotypes. This can be achieved by either killing or weakening a selected agent

by decreasing its strength. For this purpose, a deﬁned matching function is used to calculate the

similarity of a tested agent to a lymphocyte-agent (e.g., the percentage of similar genes). Lym-

phocyte agents are created after the death of an agent and are given a mutated variant of its

genotype. Over a period of time, the lymphocyte patterns that recognize “good” agents (possessing

high amounts of energy) are eliminated. In this way, the evolution promotes those lymphocyte

agents that bear a resemblance to “bad” agents so that they can be continuously removed from the

system – thus leaving the “good” agents intact. This approach is useful for applications in which

the ﬁtness evaluation is time-consuming, as the operation of lymphocyte agents is less expensive.

The elitist evolutionary multi-agent system for multi-objective optimization is another hybrid

of EMAS that was introduced in [15]. The main idea behind this was to create a ranking of the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ApplyingAutonomousHybridAgent-basedComputingtoDicultOptimizationProblemsMateuszGodzik,JacekDajda,MarekKisiel-Dorohinicki,AleksanderByrskiAGHUniversityofScienceandTechnology,Al.Mickiewicza30,30-059Krakow,Poland,{godzik,dajda,doroh,olekb}@agh.edu.plLeszekRutkowskiInstituteofComputerScience,AGHUnivers...

展开>> 收起<<

Applying Autonomous Hybrid Agent-based Computing to Difficult Optimization Problems.pdf

共29页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Applying Autonomous Hybrid Agent-based Computing to Difficult Optimization Problems

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: