Designing Genetic Algorithms

Recently I presented a conference paper in ISCC 2021, it is on the Service Function Chain Embedding problem; find it in IEEEexplore or here. The problem is handled efficiently using a genetic algorithm. Here are a few empirical remarks about how to design efficient and effective GAs which I gained from working on this paper.
The issue with designing GAs is that their operation is not sufficiently explained and the efficiency of any GA design is case dependent. Any innovation applied on a GA implementation may work well on a problem and fail on many others.

At first there is the population generation. The objective of a GA is to approximate the goal solution of a problem among all the possible solutions in the solution space of the problem. So, from the members of the population we have to be able to generate the goal solution by applying the genetic procedures on the population. Then the initial population will have to be directed to the part of the solution space that contains the goal and for this reason we have examine whether it is more efficient to generate the population heuristically instead of a randomized generation which is the common practice.

Preserving original chromosomes and best solutions. The procedures of crossover and mutation were originally designed so as to affect the members of the initial population. During crossover, the parent chromosomes generate offspring that may replace them in the population. Also during mutation the genotype of a chromosome is affected and this results the replacement of the original solution that the chromosome represents by a new solution that the mutated chromosome represents. Moreover, the randomized operations of the GA may reject or replace a good solution.
Having these in mind, my proposition is to preserve the best solution generated during a generation regardless of how the new population will be formed. Also the generation of new offspring and new mutated chromosomes should not replace the previous ones. Add the new chromosomes in the population along with the older ones and let the selection procedure decide which will survive in the next generation.

Premature convergence. There are many reasons for the premature convergence of the population in an undesirable solution. One technique of limiting this phenomenon and achieving a more stable behavior for the algorithm is the multiple execution of the algorithm and the further procedure of all the outputs.  The outputted solutions from all the executions maybe combined so as to generate a probably better solution (this was my approach) or you may just pick the best one for the final output.

Parameter tuning. GAs are multiparametric algorithms and the values of these parameters determine their performance; the parameters are the number of generations, population size, crossover and mutation probabilities. There are two ways to determine the best valuations for these parameters. Either by extensive experimentation or by using an optimization procedure like the one described in my earlier post.

How to tune up the parameters of a multiparametric algorithm

Genetic algorithms are multiparametric procedures. Their operations depend on a variety of parameters these usually are the size of the initial population, the number of generations, probability thresholds that define the crossover and mutation procedures and sometimes heuristics that some developers use. One of the open problems on genetic algorithms is the determination of the optimal values for these parameters. It is also called parameter tuning.
Like genetic algorithms, there are other multiparametric were the determination of the optimal values for their parameters is crucial for their operation. In all the above cases, sensitivity analysis is used for reaching optimality.
As parameter tuning is actually an optimization problem and genetic algorithms are optimization techniques, I thought it would be interesting to build a genetic algorithm for parameter tuning. The result of this work may be found here and it is released as an open source project.
The tuning algorithm examines the program that implements some multiparametric algorithm as a black box. The internal operations of the program are not examined; it only considers the output of the program given some valuation on its parameters. The population of the tuning algorithm consists of set of such valuations. It is an effective approach as I have tested it extensively.
It is a very interesting approach as we do not have to consider the functionality of the program under study, as the tuning algorithm adapts its functionality on the program. And this is the essence of artificial intelligence; the algorithms have to adapt to their subject of study.
When the program under study implements a genetic algorithm then we have a genetic algorithm that tunes up another genetic algorithm, which is a cool idea.
Of course the tuning algorithm is also multiparametric, but in it we do not seek optimality. It is enough to set some high values on its parameters, wait some time until it terminates and compute the optimal values for the program. Then run the program with optimal performance.

 

 https://github.com/rodispantelis/GeneticAlgorithms

A thesis on virtual network embedding with genetic algorithms

Recently I finished my master thesis which is a study on the problem of virtual network embedding (VNE). It concerns the virtualization of network resources and topologies so as to create a fully functional virtual network embedded in a detacenter, instead of using a physical stand alone network. There are many advantages in this approach as it is much easier to update and maintain virtual devices and links instead of physical ones.

There are many ways to map virtual on physical resources, a relatively small virtual topology may be embedded in many ways in the physical network of a datacenter. The problem of VNE concerns the finding of the ideal mapping so that virtualized network will have the optimal performance.

It is a hard problem to solve so traditional analytical methods are inefficient for its solution. Artificial intelligence methods provide in such cases good and efficient solutions. In the thesis I developed a genetic algorithm that approaches the problem as an optimization problem and provides good practical solutions. 

My thesis is written in Greek and is accessible in the repository of the Hellenic Open University.  A direct download of the paper is possible in this link.

A Fibonacci complexity class

While working on a project that will come out soon, I developed an algorithm with strange asymptotic behavior. In one of the functions of the algorithm there was an arithmetic progression that had to be computed. It was not a big deal as it concerned small sets of numbers each time, at least that's what I thought.

So instead of using the formula of arithmetic progression, I just put a recursive function for it. Something like

int d = 1000;
public void progression(a){
    while(d>0){
         progression(a+1);
    }
    d--;

}
progression(0);

Where d was proportional to the input.

It worked fine, but it was slower than it should be. The reason was that the progression was computed quite a lot of times and eventually such a simple function was a huge computation burden. I was really surprised to discover that the asymptotic behavior of the algorithm could be described by the Fibonacci sequence.
So that, given n input the complexity of the algorithm was O(f(n)∙c), where f(n) is the n-th member of the Fibonacci sequence and c is constant.
After replacing the function with the formula of arithmetic progression the complexity became polynomial, thankfully. 

There are two remarks about all these.

An innocent, simple and naive function may become a problem. We have to be careful on how many times this function will be executed.

Although the first edition of the algorithm was not optimal, there comes the question. Could we define a Fibonacci complexity class? Perhaps even find problems in this class.

A function for the Fibonacci sequence

A very fast and easy function to compute Fibonacci sequence

import java.math.BigInteger;

public class main {
    int cnt=0; 
    public static void main(String[] args) {
        main m=new main();
        m.f();
    }
   
    public void f(){
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        System.out.println("F("+cnt+"): "+0);
        cnt++;
        System.out.println("F("+cnt+"): "+1);
        cnt++;
        while(cnt<22001){
            BigInteger i = new BigInteger("0");
            i=i.add(a);
            i=i.add(b);
            a=b;
            b=i;
            cnt++;
        }
        System.out.println("F("+(cnt-1)+"): "+b);
    }
}

The output, the 22000th member of the sequence

F(22000):

23911151843088049549559913282124240747696450497332393096044892530723732731293925768111253903890731043326256888603201506944633327289997819833277130504901675470982030552507094162859800238507116975505854341394434948447565033026221210674687237739231690676803475798182981709459374260692436901977628581806475354563630219526845715243350120708966860434133018586240550140499321343707423004223534607204678776111145268537233116243802761082543246510402792429498707827152647989073216179648475243965598252066378230654130470829925986857896675242722600485435164105264916456225839778968745829788512608356363913804761755901467120731200188413083136579975059928902776220812920982189971242379916708698973621766751597334216368620508938142664716772647688988834270374687235249785796824594603884916806990714534340114784869357840251209972361365742785864148242067483656445079559019489390577428621648443326010160477386933121033620560251402766516093547505148407529090149475348773752540043271767234242084292100628738483524181221019416392799181393231992347653438406600914228647401007351836588160487756479497407968315031381589638689295174823322470087642165598672121365266344137564858444622711576081771078496641844937390545682240273855295137238355228099317669135050155578932164209299731907594076460356882408869295135953607469229651099120705693263857034687843626991261121860614751345764505435552449681904020194972948652249854216623551013979700998791070339585263264828474927294673678682855378403136525049646034651097985005523792023353505230733318315806249870620106255127740873138847984020791508370779261660785053242257951531507791170889410085082494377608208359506865872052269194573000651768246582561397589379054459666059728582161757153393761840155076715427874951737024712380325595601597280455609229448744861922777558470731225112774660744411373183007786591379470772659610931545615527361828527091916649882203801119543947473205919119948687005839582793430636346335172367632567614224230754519059566437786383250603562336173795450845023555052163775749567488680209929301733953771659440841851896501176310938478061013508743746794886211545059385083016686715569969754105054345618188437480456355103779247725818147048349484128145728116464124348995944145983490657741814168978702539394407772782423978914262812859165776960650497186523875998775018517623119052276070479290941716138770758463104282213404679330007239145717905126309090972993970782474750784981648644639346866248972640808995649185451943534239803644658697695716458521133485188727182407257352988202971646888599939358651008064484936913916373530359894095131542041397727523148718163746575229775017491009940588025249473123594753441211634435730001790835648327090911035577452758024952482629199328590011397832889757271508213625527057331090954110825073969299898958013994599894944208687850453500173980744223000760078898697128052192071515006870831715957325971845783409157683811011917636814704595836802955582938763983561376453999740428687093957605525631048148288024553370500665522100169024309239057322581866840037497559911574765827496593193700042249031389395129435568195231113075207830333318500469629193676005498811061550348234102052774122312886541766341471582469457347117636205703661078984515116258554803095676657019285090837775746036193164235341465548098904615127611062939206161346093617265405906367027661546845621356149559040798776562241563525511725505792648393371898115939776591096309370497408492873254883402409802564872039524422858633347863626333558155009162515951780107533626468012894434520530192845273457409548744656177387603307356149287599938730196582636274410931646393247886112418444661056857161146184933011078210524893794117348746892516723498126540948178477524603638775070638523850390891025039264400618873393052111880108096369408947789274041790558597294722651729924404836342862376149286822275330813331363925609055924677777163416615796764181780714265864396474084320765015608284585854217131086151555790325994153510435163207497453674171928909161205383175664268065518581620152617418382937870516278875447542815346729709387258529667056688675843466545834345387745629279011899890664127165078236901460104874038389111495950291594316779654469302636244158996341777359509518944948859542336178551804878882015290324970263731030303062802591853791022670735831866555863543199284768114955047509691099289344617944901044767695479022055197983956300649586454906832181127379710025435852700124842320460296470665284849646627146368239854763930002211169617338509922746447728861929093704279396632724922533039876469981523255796252507976652376398665656696184253857275835860915242223337528463584609575885682566329602411550875