Author name cluster

Dogan Corus

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAAI Conference 2025 Conference Paper

Fast Contiguous Somatic Hypermutations for Single-Objective Optimisation and Multi-Objective Optimisation Via Decomposition

Dogan Corus
Pietro S. Oliveto
Donya Yazdani

Somatic Contiguous Hypermutations (CHM) are a popular variation operator used in artificial immune systems for optimisation tasks. Theoretical studies have shown that CHM operators can lead to considerable speed-ups in the expected optimisation time compared to the traditional standard bit mutation (SBM) operators used in evolutionary computation for both single-objective and multi-objective problems where it is advantageous to mutate large contiguous areas of the genotype representing the candidate solutions. These speed-ups can make the difference between polynomial and exponential runtimes, but come at the expense of the CHM operator being considerably slower than the SBM operator in easy hillclimbing phases of the optimisation process, when small areas of the genotype have to be mutated for progress to be made. In this paper we present a Fast CHM operator that is asymptotically just as fast as traditional SBM for hillclimbing yet maintains the efficacy of the standard CHM operator when large jumps in the search space are required to make progress efficiently. We demonstrate such efficacy on all applications were CHM has been previously studied in the literature.

PDF Details DOI

TCS Journal 2020 Journal Article

When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms

Dogan Corus
Pietro S. Oliveto
Donya Yazdani

We present a time complexity analysis of the Opt-IA artificial immune system (AIS). We first highlight the power and limitations of its distinguishing operators (i. e. , hypermutations with mutation potential and ageing) by analysing them in isolation. Recent work has shown that ageing combined with local mutations can help escape local optima on a dynamic optimisation benchmark function. We generalise this result by rigorously proving that, compared to evolutionary algorithms (EAs), ageing leads to impressive speed-ups on the standard Image 1 benchmark function both when using local and global mutations. Unless the stop at first constructive mutation (FCM) mechanism is applied, we show that hypermutations require exponential expected runtime to optimise any function with a polynomial number of optima. If instead FCM is used, the expected runtime is at most a linear factor larger than the upper bound achieved for any random local search algorithm using the artificial fitness levels method. Nevertheless, we prove that algorithms using hypermutations can be considerably faster than EAs at escaping local optima. An analysis of the complete Opt-IA reveals that it is efficient on the previously considered functions and highlights problems where the use of the full algorithm is crucial. We complete the picture by presenting a class of functions for which Opt-IA fails with overwhelming probability while standard EAs are efficient.

Details DOI

AIJ Journal 2019 Journal Article

Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem

Dogan Corus
Pietro S. Oliveto
Donya Yazdani

Typical artificial immune system (AIS) operators such as hypermutations with mutation potential and ageing allow to efficiently overcome local optima from which evolutionary algorithms (EAs) struggle to escape. Such behaviour has been shown for artificial example functions constructed especially to show difficulties that EAs may encounter during the optimisation process. However, no evidence is available indicating that these two operators have similar behaviour also in more realistic problems. In this paper we perform an analysis for the standard NP-hard Partition problem from combinatorial optimisation and rigorously show that hypermutations and ageing allow AISs to efficiently escape from local optima where standard EAs require exponential time. As a result we prove that while EAs and random local search (RLS) may get trapped on 4/3 approximations, AISs find arbitrarily good approximate solutions of ratio ( 1 + ϵ ) within n ( ϵ − ( 2 / ϵ ) − 1 ) ( 1 − ϵ ) − 2 e 3 2 2 / ϵ + 2 n 3 2 2 / ϵ + 2 n 3 function evaluations in expectation. This expectation is polynomial in the problem size and exponential only in 1 / ϵ. To the best of our knowledge this is the first time performance guarantees of any AIS are proven for a classical combinatorial optimisation problem.

Details DOI