<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Theviyanthan Krishnamohan on Medium]]></title>
        <description><![CDATA[Stories by Theviyanthan Krishnamohan on Medium]]></description>
        <link>https://medium.com/@thivi?source=rss-5f7ba63fbce3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*NYKE7_7w8IEBzQBA52PeJg.jpeg</url>
            <title>Stories by Theviyanthan Krishnamohan on Medium</title>
            <link>https://medium.com/@thivi?source=rss-5f7ba63fbce3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 06:02:41 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@thivi/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Multitask Knowledge Transfer in Genetic Algorithms]]></title>
            <link>https://thivi.medium.com/multitask-knowledge-transfer-in-genetic-algorithms-50287fd60c51?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/50287fd60c51</guid>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[artificial-neural-network]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[memetics]]></category>
            <category><![CDATA[natural-computing]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sat, 04 May 2024 22:27:47 GMT</pubDate>
            <atom:updated>2024-05-04T22:42:49.016Z</atom:updated>
            <content:encoded><![CDATA[<h4>Memetic Computation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*c8bsMngxxqIZyjr9.jpeg" /></figure><p><a href="https://www.thearmchaircritic.org/mansplainings/a-primer-on-memetic-automatons">The previous article</a> discussed transferring knowledge from one completed problem to a new problem. However, such sequential transfer of knowledge requires that there exist completed problems. But there could be times when we have to solve multiple problems and it is not practical to complete those problems one-by-one so that we can transfer the knowledge sequentially. In such cases, problems exchanging their knowledge with one another simultaneously becomes beneficial.</p><p>An example of such a scenario is finding the fastest path, the shortest path, and the most energy-efficient path between two nodes in a network. These are similar problems, so the knowledge synthesized while solving one problem may help the other two problems. However, here knowledge transfer has to be omnidirectional instead of being just sequential. How can we accomplish this? It turns out, we only need to make small modifications to the Adaptive Memetic Transfer Optimizer (AMTO) we learned about in the previous article. We call this new algorithm based on AMTO Adaptive Memetic Multitask Optimizer (AM-MTO).</p><h3>Adaptive Memetic Multitask Optimizer</h3><p>In sequential knowledge transfer, we use optimal populations from previous problems. However, in multitask scenarios, we can only make use of intermediate populations. Such populations will be diverse and spread across the search space. However, some individuals in those populations will be closer to the optimal location than others. Instead of building the probability distribution from the whole population, we build a probability distribution from a cluster of individuals who show high fitness. This way we can make sure tasks transfer only useful knowledge.</p><pre>Initialize the population pg (g denotes the generation and it is 0 at the beginning)<br>Repeat <br>    If transfer interval elapsed  <br>       Encode individuals <br>       Build probability distributions using fittest individuals from populations from other problems and probability distribution of individuals in pg by learning the weight values <br>       Sample new individuals from this probability population <br>       Decode individuals to produce offspring population o<br>    else  <br>       For each individual i in pg <br>       Calculate the fitness fi <br>       Select parents q from pg based on fi<br>       Perform crossover and mutations on to produce offspring population o. <br>    Select who will make it to the next generation pg=g+1 from o, q (irrelevant if transfer interval elapsed), and (pg - q)<br>Until the termination condition is met</pre><p>Thus, AM-MTO helps us transfer knowledge simultaneously among similar problems. Now that we have discussed how we can use optimal populations from other similar problems as memes, let’s also discuss the prospect of using Artificial Neural Networks as memes.</p><h3>Artificial Neural Networks as memes</h3><p>In the concluding chapter of <a href="https://link.springer.com/book/10.1007/978-3-030-02729-2">Memetic Computation</a>, Abhishek Gupta proposes the use of Artificial Neural Networks (ANNs) as memes. In EAs, we generally represent individuals using a low-level encoding scheme. To borrow the example the book uses, let’s use the classic knapsack problem. We have objects with different weight and profit values, and we need to fill the knapsack with objects such that we maximize the profit while ensuring we don’t violate the weight constraint. In such a case, a typical encoding would be an array of binary bits with each bit specifying if the object should be included or not.</p><p>This can be unsustainable when the number of objects increases. If there are 200 objects, then we need a 200-bit array. To mitigate such issues, the book proposes the use of ANN. We first build a simple ANN that takes the profit and weight of an object as the input and outputs a confidence value. Then, we feed the profit and weight of every object to the ANN to get their confidence values. Next, we add objects to the knapsack in the descending order of their confidence values until the knapsack is full. Then we calculate the total profit of the objects in the knapsack to compute the solution’s fitness score.</p><p>To improve fitness, we need to evolve the synaptic weights of the ANN. This is what the EA tries to accomplish. We start with random synaptic weights and evolve them until we maximize the profit. In other words, we get the EA to tune the ANN. The major advantage here is that we replace binary-bit arrays with synaptic weight arrays as individuals. Since the neurons we need in an ANN are generally less than the number of objects, this results in dimensionality reduction. We can then use the ANN we train as a meme to solve another problem.</p><h3>Summary</h3><p>This ends the series of articles on memetic computation, so let’s summarize what we have learned. Memetic computation makes use of the concept of memes introduced by Richard Dawkins to further enhance EAs. While exploiting genetic evolution for optimization, we can make use of memes, i.e., knowledge and ideas to produce more optimal solutions faster. In Canonical Memetic Algorithms, this knowledge comes from expert humans who choose which knowledge to apply using their own experience. We can render this human intervention redundant by selecting the right knowledge using data. Automatons take this a step further by extracting knowledge from past solutions, paving the way for complete automation. We can improve this further by exchanging knowledge between multiple similar simultaneous problems. Finally, Artificial Neural Networks offer a promising landscape for dimensionality reduction while serving as an option for modelling memes, which can be used to solve other similar problems.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/multitask-knowledge-transfer-in-genetic-algorithms"><em>https://www.thearmchaircritic.org</em></a><em> on May 4, 2024.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=50287fd60c51" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A primer on Memetic Automatons]]></title>
            <link>https://thivi.medium.com/a-primer-on-memetic-automatons-277d9d22078b?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/277d9d22078b</guid>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[memetics]]></category>
            <category><![CDATA[artifical-intellegence]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sun, 07 Apr 2024 02:34:46 GMT</pubDate>
            <atom:updated>2024-04-09T15:21:42.935Z</atom:updated>
            <content:encoded><![CDATA[<h4>Memetic Computation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*uziceS9xmkcYzdWS.png" /></figure><p>We discussed how we leverage data to select memes <a href="https://www.thearmchaircritic.org/mansplainings/data-driven-meme-selection">in the previous article</a>. However, as we noted, in data-driven meme selection, we start the search for the solution from scratch. What an algorithm learns during its run is only applicable to that particular problem and cannot be used to improve solutions to other similar problems. Nevertheless, this is not how humans work as we apply experience gained from one problem to solve other similar problems. Accordingly, to reify Artificial General Intelligence (AGI), we should find a way to transfer knowledge from one problem to another. This is what we try to accomplish through memetic automatons.</p><p>Memetic automatons mimic humans by improving their intelligence over time by learning from previous experience and their interaction with other automatons. Consequently, instead of starting from scratch, an Evolutionary Algorithm (EA) can use a meme produced either when solving a different but similar problem in the past or by other automatons working on similar problems simultaneously.</p><p>Similarity between problems is imperative for knowledge transfer to be effective. For instance, we may use EA to find the fastest path between two nodes in a computer network. We may also use EA to find the most energy-efficient path between two nodes. This is an example of two similar problems and knowledge transfer is more likely to be profitable in such cases. On the other hand, the knowledge of a solution to an antenna-designing problem is less likely to be useful to any of these two problems.</p><h3>Unified encoding in memetic automatons</h3><p>A fundamental challenge when transferring knowledge between two different problems is the representation of the knowledge. In EAs, the solution to a problem is the population of individuals that the algorithm converged on. These individuals may be represented by different genetic encoding schemes. So, to facilitate knowledge transfer, we should convert the genetic encoding used for each problem to a unified encoding that all problems can understand.</p><p>It is not possible to come up with one unified encoding mechanism for all problems. However, random-key representation has shown significant promise in practice. In random-key representation, we use continuous values between 0 and 1 to represent an individual. For each problem, we need to come up with an encoding scheme so that we can convert the solution to this unified code and a decoding scheme to convert the unified code back.</p><h3>Using probability distribution as memes</h3><p>After encoding each individual, the encoded individuals can form a meme. However, having several individuals form a meme may not always be convenient. The book <a href="https://link.springer.com/book/10.1007/978-3-030-02729-2">Memetic Computation by Abhishek Gupta</a> proposes using the probability distribution constructed from the individuals as a meme.</p><p>We can store these probability distributions in a knowledge base and have the automatons pick the most suitable one. However, how can an automaton know which meme will be the most apposite one? We can assign weight values to the memes and learn the weight values over time so that the most suitable ones will end up with the highest weight values.</p><p>Along with the memes, the automaton also computes the probability distribution of the individuals in a given generation evolved using EA. The weighted sum of all these distributions will produce a probability distribution. The goal is to learn the right weight values so that the individuals sampled from this probability distribution will be closer to the optimal individuals in the search space. The automaton uses the Expectation-Maximization (EM) algorithm to learn these weight values. We omit the mathematical details of this algorithm to keep this article simple.</p><p>Once the automaton obtains the weight values, it can then build the probability distribution using the weighted sum of the probability distributions from other problems (memes) and the current generation of individuals. Then, the automatons sample the offspring from this distribution to produce the next generation.</p><h3>Adaptive Memetic Transfer Optimizer</h3><p>Now, how do we integrate this automaton with an EA? Enter Adaptive Memetic Transfer Optimizer (AMTO). AMTO takes an EA and runs the automaton alongside it. To that end, we set a transfer interval. This interval decides how often we should run the automaton.</p><p>We begin by following the usual steps in an EA. We start by initializing the population, and then we calculate the fitness score. Next, we select the parents, perform crossover and mutation, and repeat the whole process until the termination condition is met. However, every time the transfer interval elapses, instead of proceeding with the EA, we run the automaton. The following pseudocode provides a summary of this algorithm.</p><pre>Initialize the population pg (g denotes the generation and it is 0 at the beginning)<br><strong>Repeat</strong><br>    <strong>If transfer interval elapsed </strong><br>        Encode individuals <br>        Build probability distribution using memes and probability distribution of individuals by learning the weight values <br>        Sample new individuals from this probability population <br>        Decode individuals to produce offspring population o<br>    <strong>else</strong> <br>        For each individual i in pg<br>        Calculate the fitness fi<br>        Select parents q from pg based on fi<br>        Perform crossover and mutations on q to produce offspring population o. <br>    Select who will make it to the next generation <strong><em>pg=g+1</em></strong> from <strong><em>o</em></strong>, <strong><em>q</em></strong> (irrelevant if transfer interval elapsed), and (<strong><em>pg-q</em></strong>)<br><strong>Until the termination condition is met</strong></pre><p>The transfer interval allows us to tune the influence of memes in moving toward the solution space in the search space. By producing individuals via genetic evolution and sampling from probability distributions of solutions to previous problems, we expedite the optimization process.</p><p>However, we are transferring knowledge only from solutions to previous problems. We call this sequential knowledge transfer. Can we solve multiple different yet similar problems simultaneously and transfer the knowledge among these problems at the same time to hasten the process of optimization? This is what we will be discussing in the next article.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/a-primer-on-memetic-automatons"><em>https://www.thearmchaircritic.org</em></a><em> on April 7, 2024.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=277d9d22078b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Data-driven meme selection]]></title>
            <link>https://thivi.medium.com/data-driven-meme-selection-b9be439ed862?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/b9be439ed862</guid>
            <category><![CDATA[artificalintelligence]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sun, 03 Mar 2024 01:30:48 GMT</pubDate>
            <atom:updated>2024-03-03T01:45:40.732Z</atom:updated>
            <content:encoded><![CDATA[<h4>Memetic Computation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FJqjnbWergtlRHaB.jpeg" /></figure><p>We explored the idea of memetic computation briefly in <a href="https://www.thearmchaircritic.org/mansplainings/an-introduction-to-memetic-computation">the previous article</a>. We learned that Canonical Memetic Algorithms (CMA) need a human expert to select an appropriate meme and that it is a major drawback in our pursuit of Artificial General Intelligence (AGI). In this article, we will discuss how we can use data to select memes automatically.</p><p>As we saw in the previous article, the role of the human expert is to select the most suitable meme from a pool of memes. The expert makes the selection based on their knowledge. They must have acquired their knowledge both through their own experience and that of other experts. Experience is essentially the data one gathers through observation. Consequently, by collecting data on the performance of different memes, we will be able to automatically pick the best meme. We call this data-driven meme selection.</p><p>There are two common ways of doing this. One is sub-problem decomposition, and the other is reward-proportionate roulette wheel selection.</p><h3>Sub-problem decomposition</h3><p>In sub-problem decomposition, we begin by randomly choosing a meme and using it on an individual. Then we compute the difference between the fitness score of the individual before and after applying the meme. We call this difference a reward. We store this reward value along with the individual and the meme in a database.</p><p>As we apply this process to several individuals across multiple generations, we will have accumulated a substantial amount of data. Then, instead of randomly selecting a meme, we can select the most appropriate meme based on this data. To that end, when we select a meme to apply to an individual, we first need to find individuals in the database who are closer to the concerned individual. In other words, we need to find individuals in the neighborhood of the concerned individual in the search space. We can do this by using any appropriate distance measure such as Euclidean distance.</p><p>Once we find the neighbors of the individual, we then pick the neighbor with the highest reward value. Next, we choose the meme applied to the neighbor and apply it to the individual. The intuition here is that the meme that brought about the highest fitness improvement among the neighbors is likelier to have a similar effect on the individual. The number of neighbors we should consider here is a tunable parameter.</p><h3>Reward-proportionate roulette wheel selection</h3><p>The reward-proportional roulette wheel selection also makes use of the reward data. However, in contrast to sub-problem decomposition, here, we store the reward data only against the meme. Accordingly, every time we apply a meme, we add the reward values, so the reward value of a meme accumulates over time. Once we have enough data, we select a meme with a probability proportional to its accumulated reward. The higher a meme’s reward, the higher the probability of selecting it.</p><p>Thus, we engage in simultaneous learning and optimization during a run. As we progress, we not only get closer to the solution, but we also learn to do it better. This is more in line with the idea of AI.</p><h3>Evolvability measure</h3><p>As we discussed in the previous article, different combinations of memes and EA strategies such as crossover and mutation strategies can produce different outcomes. For example, we can perform mutations by randomly drawing from different probability distributions. Subsequently, we apply a meme to a mutated individual in the next iteration. So, different combinations of mutations and memes can produce different outcomes. In other words, both the meme and the nature of mutation can influence eventual fitness improvement. To find the right combination, we use the evolvability measure.</p><p>To keep this article simple, let me gloss over the mathematics behind the evolvability measure. But if you are interested in the detailed mathematics, please refer to section 3.2.1 of the book <a href="https://link.springer.com/book/10.1007/978-3-030-02729-2">Memetic Computation</a>. What we need to know is that for every combination of memes and EA strategies, we calculate the evolvability measure and apply the combination that produces the highest value.</p><h3>Meme complexes</h3><p>Until now, we have only been focusing on applying one meme to an individual. In contrast, memeplexes apply a chain of memes to an individual. For instance, we first apply one meme to an individual, then another, and so on. We choose the first meme and the subsequent memes to apply by using weight values.</p><p>We first form a memetic network topology by linking memes. The chain follows the links. That is, after selecting a meme, we select the next meme from the pool of memes that have links to the first meme. Every meme and the link between them have a weight value. Our choice of memes is proportional to these weight values. For example, we will select a meme with a probability proportional to its weight and then choose the next meme with a probability proportional to the weight of the link from the first meme.</p><p>We learn these weight values starting from an unbiased initialization. To calculate the weight of a meme, we accumulate the immediate reward upon applying the meme to an individual. To calculate the link weight, we calculate the reward after executing the whole chain of memes, divide it by the length of the chain, and accumulate this value over generations.</p><h3>Multi-surrogacy</h3><p>In certain cases, the fitness function of EAs can be expensive and time-consuming. For instance, in some engineering problems, we calculate the fitness of an individual by simulation which can take several hours. In such cases, we replace the expensive fitness function with a surrogate, which is a cheaper fitness function that can <em>predict </em>the fitness of an individual. Since this involves prediction, we generally use Machine Learning (ML) or regression models.</p><p>We can initially run the expensive fitness function for a few generations, generate data, train the ML model on that data, use the model to predict the fitness of individuals, select the most fit individuals, and evaluate their real fitness using the expensive fitness function. This way we can greatly conserve resources.</p><p>However, there can be many different ML models, and choosing a model among several others is akin to choosing one meme among several others. Instead of choosing one model, we can assign a weight value to each model and learn the weights over time so that the most suitable ones will automatically end up with higher weight values. We set the weight to be the inverse of the average generalization error over the dataset. So, the larger the error, the smaller the weight would be. As a result, models that perform better will eventually start exercising more influence on the predicted fitness score.</p><p>Even though we have now adopted a data-driven approach to choosing a meme, in all the above cases, we start our search for the solution from scratch. Although we learn as we proceed, this accumulation of knowledge is only applicable to the concerned problem. However, this is not how humans work. We solve problems and then use the experience to solve subsequent problems better and faster. So, to realize the idea of a meme completely, we should be able to transfer our experience solving one problem to another. This leads us to memetic automatons. In the next article, we will be discussing what memetic automatons are and how they work.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/data-driven-meme-selection"><em>https://www.thearmchaircritic.org</em></a><em> on March 3, 2024.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b9be439ed862" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An introduction to memetic computation]]></title>
            <link>https://thivi.medium.com/an-introduction-to-memetic-computation-7bbca22fa2c5?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/7bbca22fa2c5</guid>
            <category><![CDATA[memes]]></category>
            <category><![CDATA[artificalintelligence]]></category>
            <category><![CDATA[optimization-algorithms]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sun, 04 Feb 2024 14:55:32 GMT</pubDate>
            <atom:updated>2024-02-04T15:23:36.911Z</atom:updated>
            <content:encoded><![CDATA[<h4>Evolutionary Computation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*n_Ri2QlEqAVt3teb.jpeg" /></figure><p>Memetic computation is an extension of evolutionary computation that combines the use of memes and genes to produce better solutions. In this article, we discuss what memes are, and how they make evolutionary algorithms better, and learn about Canonical Memetic Algorithms, which are the most basic form of memetic computation.</p><p>As we have already seen in <a href="https://www.thearmchaircritic.org/mansplainings/an-introduction-to-evolutionary-algorithms-for-dummies">the previous article</a>, evolutionary algorithms are faster and more practical than exact optimization algorithms. However, a major problem with them is they are slow by modern standards, especially when compared to algorithms such as Artificial Neural Networks that produce solutions much more quickly. Besides, in certain applications, fitness functions can take a very long time to produce results, rendering evolutionary algorithms unpragmatic. For example, when used in engineering design, the fitness function may be a simulation run, which may take several hours to produce the final score.</p><p>Memetic computation tries to solve these issues by incorporating external knowledge to guide the process of evolution better. But how does knowledge make evolutionary algorithms better? We already know that evolutionary algorithms imitate the natural process of evolution to produce fitter individuals and that genes play an important part in evolution. However, in nature, genes are not the only ones that determine an individual’s fitness. The knowledge an individual acquires also informs their fitness. For instance, genes could allow an individual to run faster than an average person. However, by learning the proper sprinting technique, the individual could become even faster.</p><h3>Memes</h3><p>Knowledge is a set of ideas. These ideas can spread within a culture via imitation. Further, like genes, memes can also undergo natural selection. Consequently, over time, the fittest ideas survive while the rest disappear. Richard Dawkins proposed this concept in his book “ <a href="https://www.goodreads.com/book/show/61535.The_Selfish_Gene">The Selfish Gene</a> “. He named these ideas ‘memes’. Accordingly, memes determine an individual’s fitness just like genes.</p><p>Memetic computation draws from this concept by utilizing memes to further enhance evolutionary algorithms. This meme, i.e., knowledge may come from a human who is an expert in a domain or from solutions to past problems.</p><p>This series of articles tries to provide a very generic introduction to the world of memetic computation based on the book “ <a href="https://link.springer.com/book/10.1007/978-3-030-02729-2">Memetic Computation</a> “ by Abhishek Gupta and Yew-Soon Ong. My goal is to provide an elementary intuition about memetic computation, so I have left out the mathematical and theoretical intricacies of it.</p><p>To understand this concept better, I will be using the same framework employed by the book. First, we will be looking at the Canonical Memetic Algorithms (CMA) followed by the idea of data-driven meme selection. Next, we shall explore memetic automatons before discussing the possible future use of Artificial Neural Networks (ANN) as memes.</p><h3>Canonical Memetic Algorithms</h3><p>CMAs are the crudest form of memetic computation. They introduce memes in the form of local search algorithms chosen by an expert. Here, the knowledge comes from the experts as they decide what the most appropriate local search algorithm for a given problem is. But what is a local search algorithm?</p><p>Evolutionary algorithms perform global searches. That is, they search the whole search space and gradually narrow toward the solution. In contrast, a local search entails searching a small part of the search space. Canonical Memetic Algorithms (CMAs) combine global and local search to produce a better net output. Let’s see how they do it.</p><p>As we have already seen, in evolutionary algorithms, we generate a population of individuals and calculate their fitness score using a fitness function. A CMA selects a subset of these individuals and subjects them to local search. This local search tries to improve an individual iteratively until it meets a termination condition. In other words, a local search algorithm improves an individual by searching its neighborhood for a fitter individual.</p><p>So, in essence, CMA improves some of the individuals in the population by using a carefully selected local search algorithm. When this happens on top of the improvement made to the population through the process of evolution, studies show that we converge on a better solution faster.</p><h3>Improvement strategies</h3><p>CMAs use two different strategies to apply the improvement local search makes to individuals. The first one is<em> Lamarckian evolution</em> which replaces an individual in the population with an improved version and updates its fitness score. The second one is the <em>Baldwin effect</em> which updates the fitness score without replacing the individual. So, in effect, we end up with the same individual but with an improved fitness score. Here the fitness score indicates not the actual fitness of the individual but its potential fitness.</p><p>The following is a pseudocode of a typical CMA.</p><pre>Initialize the population <strong><em>pg</em></strong> (<strong><em>g</em></strong> denotes the generation and it is <strong>0</strong> at the beginning)<br><br>Repeat<br><br>    For each individual <strong><em>i</em></strong> in <strong><em>pg</em></strong><br><br>        Calculate the fitness <strong><em>fi</em></strong><br><br>        If <strong><em>i</em></strong> is selected for local search<br><br>               <strong><em>imod</em></strong>,<strong><em>fi_mod</em></strong> = local_search(<strong><em>i</em></strong>)<br><br>               <strong><em>i</em></strong>,<strong><em>fi</em></strong> = update(<strong><em>i</em></strong>,<strong><em>fi</em></strong>, <strong><em>imod</em></strong>,<strong><em>fi_mod</em></strong>) <em>#Lamarckian evolution/Baldwin effect</em><br><br>     Select parents <strong><em>q</em></strong> from <strong><em>pg</em></strong> based on <strong><em>fi</em></strong><br><br>     Perform crossover and mutations on <strong><em>q</em></strong> to produce offspring population <strong><em>o</em></strong><br><br>     Select who will make it to the next generation <strong><em>pg+1</em></strong> from <strong><em>o</em></strong>, <strong><em>q</em></strong>, and <strong><em>p</em></strong><br><br>Until the termination condition is met</pre><p>Even though CMAs generally provide better outcomes, one needs to be careful when employing CMAs because certain combinations of local search algorithms and evolutionary strategies may provide a worse outcome than vanilla evolutionary algorithms. For example, a local search algorithm used with the roulette-wheel selection strategy may produce a worse result. So, one needs to identify the right combination of a local search algorithm and an evolutionary strategy.</p><p>Even though CMAs improve outcomes, one of the major issues with CMAs is that they require human intervention. This is because we need an expert to select the local search algorithm. This is an obstacle in the pursuit of Artificial General Intelligence (AGI). In subsequent articles, we shall see how we can make memetic computation more autonomous.</p><h3>Summary</h3><p>Memetic computation expands evolutionary computation by using memes to improve the output. A meme is a unit of ideas that undergoes natural selection like genes. A Canonical Memetic Algorithm uses a local search algorithm to improve the fitness of a subset of individuals in the population. The local search algorithm is chosen by a human expert. So, the knowledge of the expert is the meme here. Since this involves human intervention, this algorithm is not autonomous. The upcoming articles will discuss how we can make memetic computing more autonomous.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/an-introduction-to-memetic-computation"><em>https://www.thearmchaircritic.org</em></a><em> on February 4, 2024.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7bbca22fa2c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[An introduction to evolutionary algorithms for dummies]]></title>
            <link>https://thivi.medium.com/an-introduction-to-evolutionary-algorithms-for-dummies-40eec4747b9e?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/40eec4747b9e</guid>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[optimization-algorithms]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[natural-computing]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sat, 06 Jan 2024 20:53:04 GMT</pubDate>
            <atom:updated>2024-01-06T22:17:19.774Z</atom:updated>
            <content:encoded><![CDATA[<h4>Evolutionary Computing</h4><p>Evolutionary algorithms are heuristic search and optimization algorithms that imitate the natural evolutionary process. This article puts evolutionary algorithms into context and explains their basic functionality. Consequently, we first examine why we prefer heuristic algorithms over exact algorithms. With that understanding, we then try to understand how a basic evolutionary algorithm works.</p><p>Searching and optimization problems involve finding an optimal solution to a problem in a search space. If the search space is small enough, then regular search algorithms such as breadth-first and depth-first search will suffice. However, when the search space becomes larger, such exact algorithms won’t be able to find an optimal solution within an acceptable amount of time. In such cases, we use heuristic algorithms. These algorithms employ intelligent guesses to get close to the optimal solution in a large search space.</p><h3>Heuristic algorithms</h3><p>For example, let’s assume there are more than a million different routes from city A to city B via different cities. To find the fastest route between the two cities, an exact search algorithm will try to compute the time taken via each route. However, given that there are more than a million routes, this might not be a very practical way of solving the problem. Instead, a heuristic algorithm will employ an intelligent guess to find a near-optimal solution within an acceptable time.</p><p>A greedy algorithm is a good example of a heuristic algorithm. A greedy algorithm simply takes the fastest available routes along its way until it reaches the destination. For example, from city A, the algorithm will pick the city it can reach the fastest next, and so on until it reaches city B. However, we cannot guarantee that this will find the fastest route between the two cities. For instance, let’s look at the example in Figure 1. From city A, the fastest route is to city D. However, if you choose the route to city D, you may end up taking 7 hours longer to reach city B than you would if you chose the route to city C.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*ikoMkLPeAb96AglY" /></figure><p>Consequently, heuristic algorithms cannot find the most optimal solutions to complex problems. However, their strength is their speed as an accurate algorithm that takes an unacceptable amount of time is as good as not solving at all. Accordingly, we consider lesser accuracy an acceptable compromise to make.</p><h3>Evolution in nature</h3><p>Evolutionary algorithms are a type of heuristic algorithm that use the concept of evolution found in nature to find near-optimal solutions to complex optimization problems. Let’s see how these algorithms work in general. But before that let’s understand how evolutions work in nature.</p><p>In nature, a population comprises several individuals belonging to a species. Different combinations of genes determine an individual’s characteristics. Some of these characteristics are beneficial while others are detrimental. Individuals with more beneficial characteristics survive and pass on their beneficial genes to the next generation. This way the beneficial genes become more dominant in a population. It is the natural environment that decides which genes are beneficial. In other words, nature selects the fittest genes.</p><p>As the natural environment changes, individuals may need new characteristics to survive. To produce new characteristics, you need new gene combinations. Nature produces new gene combinations through mutation and sexual reproduction. Mutation is any random ‘error’ that occurs in genes when cells multiply. Sexual reproduction is when genes from two individuals combine to produce new characteristics. Accordingly, mutation and combinations of genes from individuals produce variations in the population. Nature then selects the fittest variation. We call this whole process evolution.</p><p>For instance, a genetic mutation may have made the neck of some giraffes in a population longer. In an environment where leaves are found in very tall branches, this group of giraffes would have had a better chance of survival, resulting in their mutated genes becoming dominant in the population. Thus, giraffes evolved to have longer necks.</p><h3>Evolutionary algorithms</h3><p>Now, let’s see how we can use this knowledge to develop an evolutionary algorithm. We initially start with a random set of routes from city A to city B. We call each one of these random routes an individual. These individuals together form a population. In our example, we can consider every city in the route as a gene. For instance, a random individual in the population can have the following genes: A-E-H-G-B. As we can see, genes make up the probable solution to a problem. Our population will have several such genetic sequences. Our goal is to find the most optimal sequence.</p><p>To that end, we perform what we see in nature. First, we try to produce new individuals and then select the most fit individuals. We can use both mutation and sexual reproduction to produce new individuals. In evolutionary algorithms, we perform sexual reproduction by performing crossovers. But before performing crossovers, we decide on the set of individuals who should undergo this process. We make this decision based on how fit these individuals are. We consider an individual that can give us a better solution fitter. In our case, a better solution is a faster route. So, we can decide the fitness of individuals by computing the total time of the journey. We call the function that computes this fitness score the fitness function.</p><h3>Parent selection</h3><p>Once we find the fitness score of every individual, it’s time to select the parent individuals who would engage in crossovers from the population. Intuitively, selecting the most fit individuals should result in offspring with high fitness. However, as we saw with the greedy algorithm example, we may end up with a suboptimal solution if we get too greedy.</p><p>To get a better understanding, let’s look at these two individuals from our example: A-E-F-K-B and A-D-H-I-J-B. Let’s assume individual 1 takes 10 hours and individual 2 takes only 8 hours. We may be tempted to pick individual 2 over individual 1. However, note that the F-K-B genes of individual 1 take only 2 hours. These genes, if they crossover to another individual, may produce a fitter individual. Hence, by rejecting this individual, we are losing out on good genes. This can result in a loss of genetic diversity in the population, and we may end up with a local optimum.</p><p>At the same time, we also can’t afford to randomly select individuals since that essentially means that we are performing a random search. So, we need to find effective parent selection strategies to select parents for crossover that will provide a tradeoff between conserving diversity and moving towards the solution faster. Some of the popular strategies are <a href="https://www.thearmchaircritic.org/mansplainings/tournament-selection-in-genetic-algorithms">tournament selection</a>, <a href="https://en.wikipedia.org/wiki/Fitness_proportionate_selection">roulette-wheel selection</a>, and random selection. Roulette-wheel selection, for instance, randomly selects individuals after assigning each individual a probability proportional to their fitness. So, it ensures fitter individuals have a higher probability of getting selected, while not rejecting less fitter individuals entirely.</p><h3>Crossovers and mutations</h3><p>Once we select the parents, we perform crossovers. As the name implies, during crossovers, individuals exchange parts of them with a random pair. Several different crossover strategies exist such as one-point crossover and uniform crossover. In one-point crossover, two individuals split into two and exchange their halves to produce offspring.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*hKkiBLacqoKKYvZc" /></figure><p>Following crossovers, we mutate individuals by randomly modifying a gene of some of the individuals. This increases the diversity of the population and allows us to produce new solutions. However, too many mutations can once again veer us in the direction of a random search, so we need to perform mutations in moderation.</p><h3>Survivor selection</h3><p>Subsequently, after we produce new individuals, we need to decide on who will survive to the next generation. We do this to make sure the number of individuals across generations remains constant. We can do this using several strategies. One strategy is to allow all offspring (new individuals) to pass to the next generation. Another strategy is to select the fittest individuals from the entire population (new and old individuals) for the next generation, which means some of the offspring may die. Once we complete this, we iterate over this whole process again. We continue to iterate until either the average fitness of the population stops improving significantly or we reach a specified number of iterations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*USdqaNM_yOPEc_d1" /></figure><p>In evolutionary algorithms, we start from many different random places in the search space and slowly evolve toward the solution in the search space. With every iteration, what begins as a random search starts to gain a sense of direction before finally converging close to the optimal solution.</p><h3>Summary</h3><p>For better understanding, we summarize a generic evolutionary algorithm using the pseudocode below.</p><pre>initialize the population <strong><em>pg</em></strong> (<strong><em>g</em></strong> denotes the generation and it is <strong>0</strong> in the beginning)<br><strong>Repeat </strong><br>  For each individual <strong><em>i</em></strong> in <strong><em>pg </em></strong><br>    Calculate the fitness <strong><em>fi</em></strong> <br>    Select parents <strong><em>q</em></strong><em> </em>from <strong><em>pg</em></strong> based on <strong><em>fi </em></strong><br>    Perform crossover and mutations on <strong><em>q</em></strong> to produce offspring population <strong><em>o</em></strong> <br>    Select who will make it to the next generation <strong><em>pg+1</em></strong> from <strong><em>o</em></strong>, <strong><em>q</em></strong>, and (<strong><em>pg - q</em></strong>) <br><strong>Until the termination condition is met</strong></pre><p>In this article, we looked at the relevance of heuristic algorithms as exact algorithms cannot solve complex problems within an acceptable time. Then, we discussed how evolution works in nature briefly before understating how evolutionary algorithms work. Evolutionary algorithms start with a random set of individuals, select individuals to become parents via strategies such as roulette-wheel selection, tournament selection, etc., perform crossovers and mutations to produce offspring, and select individuals who will make it to the next generation. This process is iterated until the algorithm meets a termination criterion. Although evolutionary algorithms are capable optimizers, they do have their limitations. Let’s see how we address these limitations in subsequent articles.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/an-introduction-to-evolutionary-algorithms-for-dummies"><em>https://www.thearmchaircritic.org</em></a><em> on January 6, 2024.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=40eec4747b9e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Running multiple containers within virtual hosts in Mininet]]></title>
            <link>https://thivi.medium.com/running-multiple-containers-within-virtual-hosts-in-mininet-a9b3c3544e9b?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9b3c3544e9b</guid>
            <category><![CDATA[mininet]]></category>
            <category><![CDATA[docker]]></category>
            <category><![CDATA[virtualization]]></category>
            <category><![CDATA[containerization]]></category>
            <category><![CDATA[computer-networking]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Mon, 04 Dec 2023 07:18:51 GMT</pubDate>
            <atom:updated>2023-12-04T07:30:29.619Z</atom:updated>
            <content:encoded><![CDATA[<h4>Docker Containers</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*gyhQ2KI0F2qWIjEa.jpeg" /></figure><p>Mininet is a popular network emulator that allows us to create virtual networks using virtual hosts, switches, and controllers. Recently, I faced the need to run multiple Docker containers within virtual hosts in Mininet. This article dwells on why it is challenging and how I eventually accomplished it.</p><h3>Context</h3><p>Before we begin, let me explain my motivation. I am a researcher working on <a href="https://www.thearmchaircritic.org/mansplainings/the-nuts-and-bolts-of-service-function-chaining-sfc">Service Function Chaining</a> (SFC) and I recently set about building a testbed that I can use to evaluate algorithms used for SFC placement. For the uninitiated, SFC placement is about building a chain of Virtual Network Functions (VNFs) such as firewalls, load balancers, Intrusion Detection Systems (IDS), etc., and finding the optimal physical servers and links to embed these functions on. One server may accommodate several VNFs and we virtually link these VNFs together over the physical links to form SFCs.</p><p>I decided to use Mininet to emulate the physical substrate network. Mininet provides both virtual hosts and switches, so building a simple substrate network was straightforward. However, deploying multiple VNFs on a virtual host proved to be a challenge. This is because virtual hosts in Mininet offer only network isolation.</p><h3>The challenge</h3><p>This means Mininet doesn’t offer filesystem or process isolation. Processes running on a virtual host in Mininet actually run on the Mininet host and use the host’s filesystem. This becomes a problem when you want to deploy multiple VNFs on one virtual host, especially when you want two instances of the same VNF. To illustrate this, let’s use the following example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*YVPTH8sodMgNsM-R" /></figure><p>Two web servers and a client are connected using a switch. The web servers run a Flask application that uses a file to keep track of the number of API requests. Every time a client sends a request, the app increments this number in the file and returns it as a part of the response.</p><p>The two servers should run an instance of this application each. Ideally, we will expect each server to maintain and return its own counter values. Let’s see if that’s the case here by sending a request from the client to the two servers in Mininet.</p><p>When we run the code, we can observe that the servers return 0 and 1. This means both servers share the same file. Let’s try to send one more request to each server to confirm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*vKcK8ZMPnDTMDZvw" /></figure><p>As we can see, both servers are using the same file to persist the counter. This is because, in Mininet, virtual hosts share the same filesystem. Besides, we can also see that the two Python processes are running on the Mininet host by running the `ps -al` command.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*5os-lmqqWVrrHtWh" /></figure><h3>Using Docker containers as virtual hosts</h3><p>We can try to implement network, filesystem, and process isolation on virtual hosts. However, since containerization already facilitates this, why don’t we simply commission its service? Here is where <a href="https://containernet.github.io/">Containernet </a>comes in handy. Containernet is a fork of Mininet that replaces the virtual hosts in Mininet with Docker containers offering us complete isolation. You can find a guide on how to get started <a href="https://github.com/containernet/containernet">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*JqcV4F2cM-YSV08V" /></figure><p>So, let’s see if Containernet can solve our issue. I am going to now use the Python Docker library to build our web server into a Docker image and replace the two virtual hosts in the previous example with two Docker containers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*-4F9UJvAPcOkMBiV" /></figure><p>This time, as expected, the servers have returned two independent counter values as they maintain their own files thanks to the filesystem isolation provided by Docker.</p><h3>Docker in Docker containers</h3><p>However, this is not enough. Even though each virtual host is now self-contained, running multiple VNFs within a container is still going to pose issues. For starters, running two instances of the same VNF within a container will be problematic as there exists no process or filesystem isolation within a container. Ideally, we should deploy VNFs as containers to overcome such issues. However, since we use a container itself as a virtual host, this means that we will have to deploy containers within containers.</p><p>This may seem wild, but it is very much a possibility. In fact, Docker has an official image that allows you to spin up Docker containers within a Docker container. You can access these images by using the `dind` tag. However, there is a catch.</p><h3>Enabling the privileged mode</h3><p>To deploy containers within containers, we have to run the host container in the privileged mode. Doing so grants containers access to the kernel space of the host Operating System. We can do this easily by passing the `-privileged` flag to the Docker `run` command. However, Containernet doesn’t allow you to start a container in the privileged mode and <a href="https://github.com/containernet/containernet/blob/31eeb7562b727abaef3001234a9eda82163a2611/mininet/node.py#L828">this is disabled by default</a>.</p><p>Consequently, the only way to resolve this is by modifying the code. There is already a <a href="https://github.com/containernet/containernet/pull/249">Pull Request</a> to the repository with the necessary changes to add this feature but it has not been merged yet. So, either you will have to modify the code yourself and run it or you can use my <a href="https://github.com/thivi/containernet">fork</a> of the repository that contains the changes.</p><h3>Running multiple containers within a virtual host</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*YfXvESMzAwIMwupg" /></figure><p>Let’s now see if we can run two instances of the web server within one Docker container successfully. To that end, I will be using a server and a client connected by a switch. The server is a Docker container that runs the Docker-in-Docker image. Two instances of the web server will be deployed as Docker containers within this Docker container.</p><p>Here, one container is mapped to port 80 on the host and the other to 8080.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/0*O5PwROKlUpimiaQJ" /></figure><p>As we can see, we are able to run these two servers without any issues as Docker containers within the host Docker container. Accordingly, we can use Containernet and the Docker-in-Docker image to deploy multiple containers within a virtual host in Mininet. By using this strategy, I can now emulate an environment where multiple VNFs are deployed on a physical server.</p><h3>Summary</h3><p>In this article, we first saw the motivation behind needing to run multiple containers within a virtual host and the challenge posed by the absence of filesystem and process isolation in Mininet hosts. Subsequently, we discussed how we can leverage Containernet to use Docker containers as virtual hosts in Mininet, providing us with complete isolation. Finally, we dealt with how we can use the Docker-in-Docker image to deploy multiple VNFs within the host container. You can find all the code I used in this article <a href="https://github.com/thivi/containernet-dind">here</a>.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/tech-journal/running-multiple-containers-within-virtual-hosts-in-mininet"><em>https://www.thearmchaircritic.org</em></a><em> on December 4, 2023.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9b3c3544e9b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The nuts and bolts of Service Function Chaining (SFC)]]></title>
            <link>https://thivi.medium.com/the-nuts-and-bolts-of-service-function-chaining-sfc-c5661f68950b?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/c5661f68950b</guid>
            <category><![CDATA[sofware-engineering]]></category>
            <category><![CDATA[5g]]></category>
            <category><![CDATA[virtualization]]></category>
            <category><![CDATA[telecommunication]]></category>
            <category><![CDATA[computer-networking]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sun, 12 Nov 2023 01:38:46 GMT</pubDate>
            <atom:updated>2023-11-12T02:32:31.000Z</atom:updated>
            <content:encoded><![CDATA[<h4>Computer Networking</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_8yDcsvLcJhAWUXm.jpeg" /></figure><p>Service Function Chaining (SFC) leverages Network Function Virtualization (NFV) and Software Defined Networking (SDN) to create a programmable and dynamic network paradigm that allows networks to keep up with modern demands. This article briefly discusses the importance of SFC, how it works, and its architecture.</p><h3>NFV and SDN in SFC</h3><p>In a traditional network, network functions such as firewalls exist as hardware devices, and there exists a tight coupling between network functions and the network infrastructure. Since these functions exist as hardware devices, we cannot easily add or remove them. Scaling them both vertically and horizontally also becomes a problem. This is because such actions entail disrupting the network and manually reconfiguring the network topology, neither of which is acceptable in a real-world environment.</p><p><a href="https://www.thearmchaircritic.org/mansplainings/what-is-network-function-virtualization-nfv">Network Function Virtualization</a> (NFV) overcomes this problem by allowing us to deploy network functions as Virtual Network Functions (VNFs) on commercial servers. This allows us to add, remove, and scale network functions easily with minimal service disruption. However, NFV still doesn’t address the topological changes that we may have to make.</p><p>Here is where Software Defined Network (SDN) comes into the picture. SDN decouples the control plane of a networking device such as a switch from the data plane and centralizes it in a controller. This means switches only forward data packets to the right destination while the controller takes the forwarding decisions. We can programmatically control these controllers, meaning that we can control the entire network programmatically.</p><p>SDN provides the missing piece so that we can now add, remove, and scale network functions while not having to manually configure the network topology. Let’s now see how SFC uses both NFV and SDN to accomplish this in detail.</p><h3>Service Overlay</h3><p>As we discussed earlier, the problem with traditional network functions is their tight coupling with hardware. SFC addresses this by creating a virtual layer above the physical network. We call this virtual layer a service overlay. Since it is virtual, we can programmatically control this. NFV virtualizes network functions and makes it a part of the overlay. On the other hand, SDN helps establish virtual links between these network functions by programmatically establishing links over the physical network.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*UuKfD12Ygwm8jLoU" /></figure><p>The above diagram shows a service overlay on top of a physical network. Here firewall, Intrusion Detection System (IDS), and load balancer are VNFs. We deploy these VNFs on servers on the physical network using NFV. Then, we use SDN to programmatically establish links between the servers so that we can chain these VNFs together to form a Service Function Chain (SFC).</p><p>The Internet Engineering Task Force (IETF) defines SFC as “the definition and instantiation of an ordered set of service functions and subsequent ‘steering’ of traffic through them”. SFC has its applications in 5G network slicing, mobile core networks, data centers, and edge computing. Just like how the cloud has replaced on-prem service deployments, with SFC, enterprises can outsource their on-premise network functions to service providers. The service providers can rapidly spin up the needed SFCs for their customers, abstracting away the deployment and maintenance tasks.</p><p>Accordingly, a client who needs a firewall, IDS, and load balancer for their web servers can simply request a service provider for an SFC consisting of these network functions and have the traffic routed through the SFC before reaching their servers. However, it is a challenge for a provider to cater to multiple such SFCs. IETF introduced an <a href="https://www.rfc-editor.org/rfc/rfc7665">architecture for SFCs</a> to help with this.</p><h3>SFC Architecture</h3><p>An SFC architecture consists of <strong>Service Functions (SFs)</strong>, <strong>Service Classification Function (SCF)</strong>, <strong>Service Function Forwarders (SFFs)</strong>, and <strong>SFC Proxies</strong>. Service Functions are VNFs that we deploy on servers. The Service Classification Function classifies incoming traffic and decides which traffic needs to go through which SFC. This helps when a network caters to different clients and requests. To route traffic through different SFCs, SCF uses <strong>SFC encapsulation</strong>. An SFC encapsulation tells which <strong>Service Function Path (SFP)</strong> a traffic flow belongs to. An SFP is the path taken by a traffic flow belonging to an SFC.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*xfI50MFZPeiQia3q" /></figure><p>An SFP can be specific or abstract depending on how the operator designed it. Generally, it is an abstract definition of a path. If we consider our previous example, an SFP could describe the path as firewall &gt; IDS &gt; load balancer. However, a <strong>Rendered Service Path (RSP)</strong> provides an explicit description of the path that a traffic flow takes. This includes the specific instances of VNFs and the SFFs it needs to go through.</p><p>An SFF is responsible for one or more SFs. The traffic meant for an SF has to first go through the corresponding SFF. The SFF then decides which SF to forward the traffic to. Once the SF processes the traffic, it forwards it back to the SFF. If the next VNF in the SFC also belongs to the same SFF, then the SFF forwards the traffic to the next SF. If not, the SFF forwards the traffic to the SFF of the next SF.</p><p>At the same time, there could be legacy SFs in the network that may not be aware of SFCs. In such cases, we use an <strong>SFC proxy</strong>. The proxy removes the SFC encapsulation before forwarding the traffic to the legacy SF. Once it receives the processed traffic, it re-encapsulates the traffic and forwards it to the next entity.</p><h3>Summary</h3><p>This article introduced the idea of Service Function Chaining (SFC), discussed its importance, and explained the SFC architecture briefly. SFCs make use of NFV and SDN to create a virtual layer consisting of VNFs and virtual links between them. This allows operators to quickly deploy, manage, and scale network functions. This means that enterprises can now outsource their network functions and have them quickly set up for them by service providers. The SFC architecture provides a framework to route traffic from multiple such enterprise clients through SFCs meant for them. Given the many potential benefits they offer, SFCs have a bright future in 5G, mobile core networks, data centers, and edge computing.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/the-nuts-and-bolts-of-service-function-chaining-sfc"><em>https://www.thearmchaircritic.org</em></a><em> on November 12, 2023.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c5661f68950b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What is Network Function Virtualization (NFV)?]]></title>
            <link>https://thivi.medium.com/what-is-network-function-virtualization-nfv-e44ce5921cf0?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/e44ce5921cf0</guid>
            <category><![CDATA[virtual-networking]]></category>
            <category><![CDATA[network-function-virtual]]></category>
            <category><![CDATA[cloud]]></category>
            <category><![CDATA[5g]]></category>
            <category><![CDATA[computer-networking]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Sun, 22 Oct 2023 00:36:14 GMT</pubDate>
            <atom:updated>2023-10-22T00:43:52.484Z</atom:updated>
            <content:encoded><![CDATA[<h4>Computer Networks</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*05Iwikd572ZpW7c4.jpg" /></figure><p>Network Function Virtualization (NFV) is the latest chapter in computer networks that tries to solve some of the pressing concerns with traditional networks. What is NFV and why is it all the rage? How does it differ from traditional networks? How does it benefit us? Let’s try to answer these questions in this article.</p><h3>The problem with traditional networks</h3><p>Traditional computer networks suffer from hardware middleboxes. Hardware middleboxes are network functions such as firewalls, Network Access Translation (NAT), load balancers, and Intrusion Detection Systems (IDS) that are available as hardware devices. Network administrators deploy these hardware middleboxes in networks to provide network solutions. For example, a web host could deploy a firewall and a load balancer in front of the web servers to secure the servers and satisfy QoS requirements. So, what’s wrong with them?</p><p>The network functions in and of themselves are not a problem. The problem is the fact that network administrators have to deploy them as dedicated hardware devices. So, deploying new network functions means introducing new hardware, which is going to consume space. Besides, the power consumption of the network also goes up as the number of functions increases. Administrators also have to reconfigure the network every time they have to insert a new function. Scaling functions dynamically according to demand is also not practically possible as it requires manual configuration.</p><p>Such issues hold back innovation. Using new network protocols is not possible without upgrading to the latest hardware. This leads to protocol ossification. This can not only impact the revenue of the network providers, but it can also hold the industry as a whole back. So, how do we fix this?</p><h3>Network Function Virtualization (NFV)</h3><p>Enter NFV. NFV tries to solve the issue of hardware middleboxes by virtualizing the network functions. Network administrators can then deploy these Virtual Network Functions (VNFs) on commercial servers. This offers a lot of advantages. To begin with, this reduces the Capital Expenditure (CAPEX) as network operators simply need to purchase software instead of entire hardware. Administrators can also deploy multiple VNFs on one server, greatly cutting down the space and power requirements. This reduces the Operating Expenses (OPEX). But the benefits don’t end here.</p><p>Since the network functions are now just software, upgrading to the latest protocols becomes easier. This addresses the issue of ossification, accelerating growth and innovation. Network operators also avoid the problem of vendor lock-in by using open-source VNFs. Moreover, removing a network function or adding a new one also becomes straightforward as this requires no topological changes. At the same time, administrators can easily scale up or down VNFs based on demand ensuring they meet the QoS requirements. This flexibility also creates an environment conducive to making networks at least partially autonomous.</p><h3>NFV Architecture</h3><p>However, NFV comes with its own unique challenges. The most important challenge is that of management and orchestration. This is about deploying VNFs on the physical infrastructure, establishing network connections between different VNFs, managing their lifecycle, scaling them up or down, and making optimal use of the hardware resources available. This is a very complicated problem, and the research community is hard at work trying to find solutions.</p><p>Nonetheless, the European Telecommunication Standard Institute (ETSI) proposed the NFV architectural framework circa 2014 to guide the development effort. This high-level framework focuses on the changes virtualization brings to an operator’s network.</p><p>The following diagram shows the NFV architectural framework.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*bGzUKp8zT19TE3Fg" /></figure><p>Now, let’s try to understand the different components of this architecture.</p><h3>VNF and EM</h3><p>VNF, as we have already seen, is a Virtual Network Function such as a firewall. An EM is an Element Management that manages a VNF.</p><h3>NFV Infrastructure</h3><p>The NFV Infrastructure (NFVI) consists of all the hardware and software that make up the physical infrastructure on top of which we deploy the VNFs. This consists of the hardware resources, the virtualization layer, and the virtualized resources.</p><p>The hardware resources are of three types, namely computing, storage, and network. Computing hardware consists of commercial off-the-shelf servers. The storage can be either the storage found in servers or Network Attached Storage (NAS). Routers, switches, and physical links form the network hardware.</p><p>The virtualization layer abstracts the underlying hardware resources and provides an interface for the VNFs to access the virtualized infrastructure. This is typically the hypervisor, but it can also be just an Operating System (OS) in a non-virtualized server.</p><p>Virtualized computing, storage, and network resources are logical partitions provided by the virtualization layer that the VNFs can utilize.</p><h3>NFV Management and Orchestration</h3><p>NFV Management and Orchestration (MANO) is responsible for deploying VNFs and managing their lifecycle. The Operations Support System (OSS), which manages the network, and the Business Support System (BSS), which takes care of the business aspects, interacts with NFV MANO to provision VNFs, manage their lifecycles, and obtain analytical information. NFV MANO consists of the NFV Orchestrator, VNF Managers, and Virtualized Infrastructure Managers.</p><h4>Virtualized Infrastructure Managers</h4><p>Virtualized Infrastructure Managers are responsible for managing the inventory of computing, storage, network, and software resources in NFVI. They also allocate Virtual Machines (VMs) to hypervisors, establish network connectivity, and manage the allocated resources. On top of this, they also engage in fault detection and data collection.</p><h4>VNF Managers</h4><p>VNF Managers are in charge of the lifecycle of VNFs which includes instantiation, updating, querying, scaling, and termination. They are also the ones that deploy VNFs on NFVI.</p><h4>NFV Orchestrator</h4><p>NFV Orchestrator orchestrates and manages NFVI through Virtualized Infrastructure Managers. In addition, the orchestrator also talks to VNF Managers to help them configure the VNFs.</p><h3>Implementation</h3><p>ETSI has initiated an effort to implement its architecture and develop an Open-Source MANO (OSM). The open-source implementation, named <a href="https://ubuntu.com/telco/osm">Charmed OSM</a>, developed in collaboration with Canonical is now available for usage.</p><h3>Summary</h3><p>In this article, we first discussed the shortcomings in traditional networks such as their cost, static nature, and protocol ossification. Then, we saw how NFV can solve the issues afflicting traditional networks by virtualizing the network functions. Finally, we discussed the NFV architectural framework and what each component in the architecture does before briefly discussing the implementation of this architecture.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/what-is-network-function-virtualization-nfv"><em>https://www.thearmchaircritic.org</em></a><em> on October 22, 2023.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e44ce5921cf0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Tournament Selection in Genetic Algorithms]]></title>
            <link>https://thivi.medium.com/tournament-selection-in-genetic-algorithms-21bb9cda0080?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/21bb9cda0080</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[natural-computing]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Fri, 29 Sep 2023 22:59:19 GMT</pubDate>
            <atom:updated>2023-10-01T02:47:32.932Z</atom:updated>
            <content:encoded><![CDATA[<h4>Genetic Algorithms</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*5tQpmaGD663CqGw7.jpeg" /></figure><p>Tournament selection is one of the many selection strategies we use in Genetic Algorithms (GAs) to select individuals for crossover. In this article, we will take a quick look at GAs, selection strategies, and finally learn about tournament selection in detail.</p><h3>Genetic Algorithm (GA)</h3><p><a href="https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3">Genetic Algorithms</a> are metaheuristic algorithms based on the natural process of evolution that we use to solve <a href="https://www.thearmchaircritic.org/mansplainings/nsga-ii-non-dominated-sorting-genetic-algorithm-ii">optimization problems</a>. This is particularly useful when the optimization problem is combinatorial and the search space is huge.</p><p>In GAs, we first randomly generate possible combinations. Every combination is called an individual. Then, we develop a fitness function that decides how fit an individual is and assigns a score to every individual in the population. Here, the population is the collective of all individuals. The fittest individual will give us the most optimal solution.</p><p>After this, we select the individuals from the population based on their fitness score to engage in crossover. A crossover is a process during which individuals exchange a portion of their combination. A selection strategy decides who gets selected and who doesn’t for crossover. Next, we select the individuals who would make it to the next generation and repeat the whole process. We continue repeating these steps either a certain number of times or until the average fitness score of the population plateaus.</p><p>The whole idea of GAs is to find the most optimal combination by having the most optimal individuals in a population exchange a part of their combination over and over again. However, the effectiveness of GAs depends on how we select these individuals. We call the strategies we use for selecting individuals selection strategies. Let’s now briefly examine what selection strategies try to do.</p><h3>Selection Strategies</h3><p>We generate individuals randomly so that we can search the search space for the optimal solution in many different places. However, if we keep searching in random places, we are never going to find the solution quickly enough. So, with time, we need to narrow down our search in such a way that we will be able to find the optimal solution.</p><p>This is the reason why we select the most fit individuals for crossover. By doing this, we hope that we will search in the right direction by following the most fit individuals. When the selected individuals engage in crossover, we randomize the solutions once again but within a limited search space. As we keep repeating this, we hope that we will continue to narrow the search space down in the right direction.</p><p>However, this may not always be the case. Sometimes, our algorithm can get stuck in a local optima. A local optima is the most optimal solution within a limited search space. The actual optimal solution, which we call the global optima, might exist in a different part of the search space. We call searching within a limited search space that gets narrower and narrower exploitation while we call searching the search space more broadly exploration.</p><h3>Exploration vs. Exploitation</h3><p>Exploitation leads to faster convergence but doesn’t guarantee that we will find the global optima. On the other hand, exploration takes a long time to converge but helps us find the global optima. For better results, we need to strike the right balance between exploration and exploitation.</p><p>It becomes exploitation if we repeatedly select only the most fit individuals for crossover. So, we use different selection strategies to find the right balance between exploitation and exploration. At the same time, each strategy may have its own parameters that we can adjust to decide the degree of exploitation and exploration.</p><p>We use the term selection pressure to refer to how far exploitation or exploration can occur. The selection pressure is proportional to the probability of the algorithm selecting the most fit individuals. When the selection pressure is high, exploitation becomes high, and vice versa. Nonetheless, we need to remember that what works for one problem might not work for another and it is important that we experiment with different selection strategies and hyperparameters.</p><p>There are various different selection strategies such as roulette wheel selection, tournament selection, rank selection, and steady-state selection. In this article, we will look at tournament selection in detail.</p><h3>Tournament Selection</h3><p>In tournament selection, we conduct tournaments among randomly selected members of a population and select the winner for crossover. We choose a winner based on the fitness score. The number of individuals participating in a tournament is a parameter that developers can tune. If the tournament size is high, then the selection pressure is high. This leads to exploitation.</p><p>The selection pressure goes up with the tournament size because a bigger tournament is more likely to have fitter individuals in the population. So, the weaker ones are less likely to win. On the other hand, in a small tournament, there is a high chance of weaker individuals contesting against each other. This reduces the selection pressure, leading to more exploration. If the tournament size is 1, then it becomes a random selection.</p><p>There are two varieties of tournament selection, namely with replacement and without replacement. Replacement refers to putting the individuals who take part in a tournament back into the population. When we perform replacement, we allow one individual to be selected more than once for crossover. This also gives the losers of tournaments additional chances of getting selected for crossover. When we don’t perform replacement, every individual gets the chance to take part in at least one tournament. This encourages exploration.</p><p>However, when we don’t replace individuals, the number of individuals we select for crossover is going to be less than the population size. This has to be accounted for when we select individuals for the next generation. Mostly, in addition to the individuals we select for crossover, we will have to use some strategy to find individuals from the current population to pass to the next generation to ensure the population size remains constant.</p><h3>Summary</h3><p>Genetic algorithms are metaheuristic algorithms based on evolution, which we use in combinatorial optimization problems. Selection strategies allow us to play around with the degree of exploitation and exploration in genetic algorithms. Tournament selection is one such strategy and it works by randomly selecting individuals for tournaments and selecting the most fit individual in a tournament for crossover. We can tune the tournament size to adjust the degree of exploitation and exploration.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/tournament-selection-in-genetic-algorithms"><em>https://www.thearmchaircritic.org</em></a><em> on September 29, 2023.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=21bb9cda0080" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[NSGA II: Non-Dominated Sorting Genetic Algorithm II]]></title>
            <link>https://thivi.medium.com/nsga-ii-non-dominated-sorting-genetic-algorithm-ii-eead0a3ac676?source=rss-5f7ba63fbce3------2</link>
            <guid isPermaLink="false">https://medium.com/p/eead0a3ac676</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[evolutionary-computing]]></category>
            <dc:creator><![CDATA[Theviyanthan Krishnamohan]]></dc:creator>
            <pubDate>Thu, 31 Aug 2023 02:23:11 GMT</pubDate>
            <atom:updated>2023-08-31T02:29:18.870Z</atom:updated>
            <content:encoded><![CDATA[<h4>Evolutionary Computing</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*S5ZpWgA4AkujMMbI.jpg" /></figure><p>Non-Dominated Sorting Genetic Algorithm II (NSGA II) is an evolutionary algorithm, which we use in multi-objective optimization scenarios. This article dwells on the nuts and bolts of the <a href="https://ieeexplore.ieee.org/document/996017">NSGA II</a> algorithm while providing a brief lowdown of the context.</p><p>Before we begin, let’s try to understand what a genetic algorithm is briefly.</p><h3>Genetic Algorithm</h3><p>Genetic Algorithm (GA) is an evolutionary algorithm that we use for optimization problems. This algorithm follows the natural process of evolution to produce a solution that is close to optimal. Since this algorithm is heuristic, this cannot find the exact global optima. Accordingly, this algorithm is most suitable for searching huge state spaces where traditional search algorithms cannot find the optimal solution within an acceptable amount of time.</p><p>Genetic Algorithm starts with a random population of individuals. Each individual is a chromosome that consists of a possible solution for a problem. For instance, let’s consider the popular <a href="https://en.wikipedia.org/wiki/Knapsack_problem">knapsack </a>problem where we have to find the right combination of items each with its weight and value so that the total weight doesn’t exceed a certain limit while we maximize the total value. When we use GA, every individual is a combination of items that is a probable solution to our problem.</p><p>A fitness function evaluates each individual and assigns a fitness value. For instance, a fitness function can compute the total value of the items in an individual while penalizing for exceeding the weight limit. Then, GA chooses the most fit individuals to produce offspring using various strategies such as <a href="https://en.wikipedia.org/wiki/Tournament_selection">tournament selection</a>, <a href="https://en.wikipedia.org/wiki/Fitness_proportionate_selection">roulette wheel selection</a>, etc. Then two parent individuals exchange a part of them with one another in a process called crossover. This helps generate new individuals with new combinations. GA repeats this whole process again and again until it meets a terminating condition. This terminating condition can be a certain number of iterations or the average fitness of the population plateauing. Once done, GA chooses the most fit individual in the population as the optimal solution.</p><h3>Multi-objective Optimization</h3><p>Now that we understand how GA works, let’s look at what multi-objective optimization is. As the name implies, this is an optimization problem that involves multiple objectives. In the knapsack problem we just discussed, our goal is to optimize the total value of items in the knapsack while making sure the total weight does not exceed the limit. Here, the total value is the objective while the total weight is a constraint. This is a single-objective optimization problem. Now, what if there is no weight limit but we want to minimize the total weight? This turns the total weight from a constraint to another objective. So, now we have two objectives: maximizing total value and minimizing total weight. This is what we call a multi-objective optimization problem.</p><p>We use the NSGA II algorithm to solve such multi-objective optimization problems. This algorithm is very similar to vanilla GA but it uses non-dominated sorting and crowding-distance sorting to select parent individuals and the individuals for the next iteration. To understand non-dominated sorting and crowding distance sorting, we first need to learn about the Pareto front.</p><h3>Pareto Front</h3><p>Let’s go back to our multi-objective knapsack problem. Here, by adding more items, we can increase the total value. But this will also increase the total weight. Remember, our goal is to maximize the total value and minimize the total weight. Consequently, we can come up with a random population of individuals and plot their weight and value in a graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*KopMkmXXiGrrgQgX" /></figure><p>As we can see, with the increase in weight, the value also increases. Even though this is the general trend, we can also observe that some individuals have lesser value while being heavier. Accordingly, some individuals are better than others.</p><p>Let’s look at the red and green individuals in the graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*CVCNyB0tQLgY70gn" /></figure><p>The red individual has individuals that both weigh less and have more value than it. On the other hand, while there are individuals that weigh less or have more value than green, there is no individual that is both less heavy and more valuable than it. In other words, red has individuals that outperform it in both objectives, but green has none. We call individuals like green non-dominated. It is worth noting that, if an individual has an equal weight but more value or equal value but less weight, then we consider it to be dominating the other individual. The following graph shows all individuals that dominate the red individual circled in red.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*uTAzGASih-hGxe9A" /></figure><p>Now, let’s try to find all the non-dominated individuals in the graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*gDDYQwlgHbhfBiyb" /></figure><p>We call the curve consisting of all the non-dominated individuals the Pareto front or Pareto optimal. None of these individuals’ weight or value can be improved without compromising on the other.</p><h3>Non-dominated Sorting in NSGA II</h3><p>Now that we understand the Pareto front, let’s look at non-dominated sorting. In non-dominated sorting, we produce several fronts sorted by their non-dominance. For instance, the green front is not dominated by any. So, this comes first on the list. Then, we can disregard this front, and try to find the next front not dominated by non-green individuals.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*K5OscKyYCDi1de1X" /></figure><p>The yellow individuals here form the second front as only the greens dominate them. Now, let’s try to find all the possible fronts.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*Ctj16rQ-CBi6LpBk" /></figure><p>So, the order of fronts is green, yellow, teal, magenta, red, and blue. Now that we understand non-dominated sorting, let’s look at crowding-distance sorting.</p><h3>Crowding-distance Sorting in NSGA II</h3><p>We use crowding-distance sorting to sort individuals within a front. To sort individuals by their crowding distance, first, we sort individuals in ascending order of their values along each axis/objective. Then, we assign the first and the last individuals a distance value of infinite. To calculate the distance of the individuals in between, we calculate the absolute normalized distance between the individual’s nearest neighbors on either side along both axes and sum them up.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/0*xAipJGdJBTKR9OIm" /></figure><p>So, if we consider the Pareto front, the crowding distance of <em>i </em>is the absolute normalized distance between ( <em>i+1</em>) and ( <em>i-1</em>) along both axes. Let’s assume that the distance along the x-axis is <em>x </em>and the y-axis is <em>y</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*q2xONyq2rweHZBTtXv4Oeg.png" /></figure><p>After finding the crowding distance, of each individual, we sort them in descending order. By assigning infinite to the first and the last individual in a front, we make sure these two values occupy the first two positions after sorting. By preferring individuals with higher distances, we make sure the individuals we choose are diverse.</p><h3>NSGA II</h3><p>Now that we understand both non-dominated and crowding-distance sorting, let’s see how NSGA II uses both of them. First, during parent selection, NSGA II uses both of these sorting methods to rank individuals. The algorithm gives individuals having a higher(better) rank in the non-dominated list a higher ranking. If two individuals belong to the same front, then NSGA II gives precedence to the individual that ranks higher in the crowding-distance list. In other words, when it comes to parent selection, NSGA II first sorts the individuals according to the non-dominated rank and then according to the crowding-distance rank.</p><p>Once, NSGA II ranks individuals, it uses binary tournament selection to pick the parents and then carries out the usual procedures we see in GA such as crossover and mutation. Once it produces the offspring population, it uses elitism for replacement. The use of elitism ensures we don’t lose individuals belonging to the higher-ranking fronts. So, NSGA II combines both the parent and offspring population and ranks the individuals according to their non-dominated ranking. This means the list we end up with contains chunks of individuals belonging to fronts in the order of their rank. The algorithm continues to select all individuals belonging to the fronts in the order of their rank until it reaches the parent population size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/0*TnOElqBdYoVewAKB" /></figure><p>However, if selecting all individuals belonging to the subsequent front results in exceeding the size of the parent population, then NSGA II will use crowding-distance sorting to select just the right number of individuals belonging to that front.</p><p>So, that concludes our discussion on NSGA II, but wait, there is one more interesting thing. One of the significant improvements NSGA II made to the original NSGA algorithm was reducing the complexity of performing non-dominated sorting.</p><h3>Algorithm Complexity</h3><p>To see if there is at least one individual that dominates a certain individual, we need to compare that individual’s value with that of every individual in the population for all objectives. This gives us a complexity of <em>O(MN), </em>where <em>M </em>is the number of objectives and <em>N</em> is the number of individuals. However, this is for one individual. If we do this for each individual, the complexity becomes . But it doesn’t end there. This is to find the first non-dominated front. Once we find the first front, we need to disregard that and find the next one until every individual becomes a part of a front. In the worst-case scenario, where one individual belongs to one front, the complexity becomes .</p><p>NSGA II reduces this complexity to Let’s see how. First, this algorithm stores the number of individuals that dominate a particular individual in a variable. Let’s call it . It also stores the individuals that this particular individual dominates in an array. Let’s call it As we have already seen, doing this for an individual entails a complexity of <em>O(MN)</em>, and repeating this process for every individual will result in a complexity of . But unlike in NSGA, we don’t need to repeat this for every front thanks to the variable and array. So, how do we identify different fronts and sort them?</p><p>Well, first NSGA II takes out all individuals whose value is 0. This means no individual dominates these individuals, so they form the first front. Then, this algorithm decrements by 1 the value of all individuals in the array of each individual in the first front. Then, it repeats the whole process to find the next front. This process goes on until NSGA II identifies all the fronts. The complexity of this process is making NSGA II faster than NSGA.</p><h3>Summary</h3><p>That’s it! We have learned how the NSGA II algorithm performs multi-objective optimization in this article. To summarize everything we have learned, NSGA II does non-dominated sorting and crowding-distance sorting to select parents and perform an elitist replacement. Non-dominated sorting ranks individuals in a population according to their dominance level while crowding-distance sorting ranks individuals within a front according to the distance between their two nearest neighbors. NSGA II reduces the complexity of the NSGA algorithm by obviating an additional iteration that it uses by persisting the number of individuals that dominate a given individual and the list of individuals that this individual dominates.</p><p><em>Originally published at </em><a href="https://www.thearmchaircritic.org/mansplainings/nsga-ii-non-dominated-sorting-genetic-algorithm-ii"><em>https://www.thearmchaircritic.org</em></a><em> on August 31, 2023.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eead0a3ac676" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>