اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAnalysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property
141
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In real-world applications, many optimization problems have the time-linkage property, that is, the objective function value relies on the current solution as well as the historical solutions. Although the rigorous theoretical analysis on evolutionary algorithms has rapidly developed in recent two decades, it remains an open problem to theoretically understand the behaviors of evolutionary algorithms on time-linkage problems. This paper takes the first step to rigorously analyze evolutionary algorithms for time-linkage functions. Based on the basic OneMax function, we propose a time-linkage function where the first bit value of the last time step is integrated but has a different preference from the current first bit. We prove that with probability $1-o(1)$, randomized local search and $(1+1)$ EA cannot find the optimum, and with probability $1-o(1)$, $(mu+1)$ EA is able to reach the optimum.
قيم البحث
اقرأ أيضاً
When evolution algorithms are used to unfold the neutron energy spectrum, fitness function design is an important fundamental work for evaluating the quality of the solution, but it has not attracted much attention. In this work, we investigated the
performance of eight fitness functions attached to the genetic algorithm (GA) and the differential evolution algorithm (DEA) used for unfolding four neutron spectra selected from the IAEA 403 report. Experiments show that the fitness functions with a maximum in the GA can limit the ability of the population to percept the fitness change, but the ability can be made up in the DEA. The fitness function with a feature penalty term helps to improve the performance of solutions, and the fitness function using the standard deviation and the Chi-squared result shows the balance between the algorithm and the spectra. The results also show that the DEA has good potential for neutron energy spectrum unfolding. The purposes of this work are to provide evidence for structuring and modifying the fitness functions and to suggest some genetic operations that should receive attention when using the fitness function to unfold neutron spectra.
This paper extends the runtime analysis of non-elitist evolutionary algorithms (EAs) with fitness-proportionate selection from the simple OneMax function to the linear functions. Not only does our analysis cover a larger class of fitness functions, i
t also holds for a wider range of mutation rates. We show that with overwhelmingly high probability, no linear function can be optimised in less than exponential time, assuming bitwise mutation rate $Theta(1/n)$ and population size $lambda=n^k$ for any constant $k>2$. In contrast to this negative result, we also show that for any linear function with polynomially bounded weights, the EA achieves a polynomial expected runtime if the mutation rate is reduced to $Theta(1/n^2)$ and the population size is sufficiently large. Furthermore, the EA with mutation rate $chi/n=Theta(1/n)$ and modest population size $lambda=Omega(ln n)$ optimises the scaled fitness function $e^{(chi+varepsilon)f(x)}$ for any linear function $f$ and any $varepsilon>0$ in expected time $O(nlambdalnlambda+n^2)$. These upper bounds also extend to some additively decomposed fitness functions, such as the Royal Road functions. We expect that the obtained results may be useful not only for the development of the theory of evolutionary algorithms, but also for biological applications, such as the directed evolution.
Many real-world applications have the time-linkage property, and the only theoretical analysis is recently given by Zheng, et al. (TEVC 2021) on their proposed time-linkage OneMax problem, OneMax$_{(0,1^n)}$. However, only two elitist algorithms (1+1
)EA and ($mu$+1)EA are analyzed, and it is unknown whether the non-elitism mechanism could help to escape the local optima existed in OneMax$_{(0,1^n)}$. In general, there are few theoretical results on the benefits of the non-elitism in evolutionary algorithms. In this work, we analyze on the influence of the non-elitism via comparing the performance of the elitist (1+$lambda$)EA and its non-elitist counterpart (1,$lambda$)EA. We prove that with probability $1-o(1)$ (1+$lambda$)EA will get stuck in the local optima and cannot find the global optimum, but with probability $1$, (1,$lambda$)EA can reach the global optimum and its expected runtime is $O(n^{3+c}log n)$ with $lambda=c log_{frac{e}{e-1}} n$ for the constant $cge 1$. Noting that a smaller offspring size is helpful for escaping from the local optima, we further resort to the compact genetic algorithm where only two individuals are sampled to update the probabilistic model, and prove its expected runtime of $O(n^3log n)$. Our computational experiments also verify the efficiency of the two non-elitist algorithms.
Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal mul
ti-objective problems. We propose the OneJumpZeroJump problem, a bi-objective problem whose single objectives are isomorphic to the classic jump functions benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. In contrast, for all problem sizes~$n$ and all jump sizes $k in [4..frac n2 - 1]$, the global SEMO (GSEMO) covers the Pareto front in $Theta((n-2k)n^{k})$ iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Runtime improvements of asymptotic order at least $k^{Omega(k)}$ are shown for both strategies. Our experiments verify the {substantial} runtime gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization.
The paper presents a solution for the problem of choosing a method for analytical determining of weight factors for a genetic algorithm additive fitness function. This algorithm is the basis for an evolutionary process, which forms a stable and effec
tive query population in a search engine to obtain highly relevant results. The paper gives a formal description of an algorithm fitness function, which is a weighted sum of three heterogeneous criteria. The selected methods for analytical determining of weight factors are described in detail. It is noted that expert assessment methods are impossible to use. The authors present a research methodology using the experimental results from earlier in the discussed project Data Warehouse Support on the Base Intellectual Web Crawler and Evolutionary Model for Target Information Selection. There is a description of an initial dataset with data ranges for calculating weights. The calculation order is illustrated by examples. The research results in graphical form demonstrate the fitness function behavior during the genetic algorithm operation using various weighting options.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
