<?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 Dr.  Samiran Bera (PhD) on Medium]]></title>
        <description><![CDATA[Stories by Dr.  Samiran Bera (PhD) on Medium]]></description>
        <link>https://medium.com/@samiran.bera?source=rss-99b9ef3643e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*sTm4QoHXNZ7xb9mYcrDL0Q.jpeg</url>
            <title>Stories by Dr.  Samiran Bera (PhD) on Medium</title>
            <link>https://medium.com/@samiran.bera?source=rss-99b9ef3643e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 19:34:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@samiran.bera/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[Backtesting Strategy for ML Models]]></title>
            <link>https://pub.towardsai.net/backtesting-of-ml-models-e558dbbea5c8?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/e558dbbea5c8</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[backtesting]]></category>
            <category><![CDATA[crossvalidation]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Sun, 15 May 2022 15:01:20 GMT</pubDate>
            <atom:updated>2022-06-15T12:37:21.153Z</atom:updated>
            <content:encoded><![CDATA[<h4>A form of cross-validation across time</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*s0IuLTyLZ4MxGWJY2Pt-YQ.jpeg" /><figcaption>Image Source: corporatefinanceinstitute.com</figcaption></figure><p><strong>Model performance</strong> is critical to any business process and must be validated periodically. To establish the efficacy of model performance, business organizations often resort to techniques such as <strong>cross-validation</strong>. Leave-one-out and k-fold cross-validation is widely used in this context. Besides these, business often needs to ascertain model performance over time, i.e., time-based cross-validation.</p><p>In this article, the purpose is to discuss time-based cross-validation methods that can be easily incorporated to measure and confirm model performance. It is known as <strong>backtesting</strong>. It is widely used in <strong>stock market analysis</strong> to predict future stock values. However, it is not restricted to it. It can be used for any time-based cross-validation purposes. The methods or strategies adapted to this end are briefly provided below. Based on the business context and data, appropriate backtesting can be adopted.</p><h3>Backtesting strategies</h3><p>There are three simple ways to backtest and validate machine learning (ML) model performance. Similar to cross-validation methods, backtest also divides the data set into training and validation sets (also referred to as hold-out data). Therefore, in a manner, backtesting can be considered an extension of cross-validation.<br>To validate ML model performance, the validation set can be identified as shown below. Each of these approaches has certain benefits and limitations.</p><h3><strong>Simple sampling strategy</strong></h3><p>In this sampling strategy, training and testing dataset are mutually exclusive, even across iterations. The benefit of this approach is its simplicity in terms of implementation and explainability. Further, it can validate ML model performance within the shortest amount of time for large datasets. However, the training of the ML models may suffer due to a lack of significant data volume for smaller datasets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3uA3vYBPHvIF2aKIGqneWg.png" /><figcaption>Simple sampling for training and testing dataset</figcaption></figure><p>The python code for simple sampling is provided next.</p><pre>def simple_batch(batch_start=&#39;2021-01-01&#39;, batch_end=&#39;2022-12-31&#39;, train_days = 30, test_days = 15 ):<br>    <br>    batch = []<br>    <br>    while True:<br>        a = pd.to_datetime(batch_start) - pd.DateOffset(days=train_days)<br>        b = pd.to_datetime(batch_start)<br>        c = pd.to_datetime(batch_start) + pd.DateOffset(days=test_days)</pre><pre>        batch.append([a, b, c])<br>    <br>        if  b + pd.DateOffset(days=train_days+2*test_days) &gt; pd.to_datetime(batch_end):<br>            break<br>        else:<br>            batch_start = b + pd.DateOffset(days=test_days+train_days)<br>            <br>    return batch</pre><p><em>Note:</em> In the python code, b represents the date where training stops and test/validation begins. Therefore, the training data and test/validation date are from a to b and b to c, respectively.</p><h3><strong>Overlapped strategy</strong></h3><p>In this sampling strategy, training and testing dataset are mutually exclusive only for the present iteration. The benefit of this approach is its simplicity in terms of implementation and explainability. Further, it can validate ML model performance within a reasonable amount of time for large datasets. However, for small datasets, the training of the ML model may suffer due to a lack of data volume.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*APrBEUygQ0RGunw1S2kyTA.png" /><figcaption>Overlapped sampling for training and testing dataset</figcaption></figure><p>The python code for overlapped sampling is provided next.</p><pre>def overlap_batch(batch_start=&#39;2021-01-01&#39;, batch_end=&#39;2022-12-31&#39;, train_days = 30, test_days = 15 ):<br>    batch = []<br>    <br>    while True:<br>        a = pd.to_datetime(batch_start) - pd.DateOffset(days=train_days)<br>        b = pd.to_datetime(batch_start)<br>        c = pd.to_datetime(batch_start) + pd.DateOffset(days=test_days)</pre><pre>        batch.append([a, b, c])<br>    <br>        if  b + pd.DateOffset(days=train_days+test_days) &gt; pd.to_datetime(batch_end):<br>            break<br>        else:<br>            batch_start = b + pd.DateOffset(days=train_days)<br>            <br>    return batch</pre><h3><strong>Aggregate strategy</strong></h3><p>In this sampling strategy, training and testing dataset are mutually exclusive only for the present iteration. Further, the training dataset of successive iterations includes all training data from previous iterations. The benefit of this approach is its ability to provide adequate data volume for ML model training. For small-size problems, it can be adopted to validate ML model performance. However, this approach can result in a longer computational time for large datasets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6cpjFl_qE7yafZzmcE5BOA.png" /><figcaption>Aggregate sampling for training and testing dataset</figcaption></figure><p>The python code for aggregate sampling is provided next.</p><pre>def aggregate_batch(batch_start=&#39;2021-01-01&#39;, batch_end=&#39;2022-12-31&#39;, train_days = 30, test_days = 15, initial_date=&#39;2020-01-01&#39; ):<br>    batch = []<br>    <br>    a = pd.to_datetime(initial_date)<br>    while True:<br>        b = pd.to_datetime(batch_start)<br>        c = pd.to_datetime(batch_start) + pd.DateOffset(days=test_days)</pre><pre>        batch.append([a, b, c])<br>    <br>        if  b + pd.DateOffset(days=train_days+test_days) &gt; pd.to_datetime(batch_end):<br>            break<br>        else:<br>            batch_start = b + pd.DateOffset(days=train_days)<br>            <br>    return batch</pre><p><em>Note</em>: The starting date for model training is fixed (which is denoted by a). Thereafter, the training date increases in each iteration similar to previous sampling methods.</p><h3>Note</h3><p>To understand backtesting in a better way, readers are advised to download any time series or similar problems and execute the above strategies. The above code will provide a training and testing set that needs to be paired with a machine learning model to train and produce forecasts. The progression steps for training and testing should ideally be more than 30 days, if not otherwise directed by the business problems. Further, the performance of the machine learning model is likely to improve for aggregate sampling. However, it is not compulsory for the other strategies — simple and overlapped where certain deviations may be visible.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e558dbbea5c8" width="1" height="1" alt=""><hr><p><a href="https://pub.towardsai.net/backtesting-of-ml-models-e558dbbea5c8">Backtesting Strategy for ML Models</a> was originally published in <a href="https://pub.towardsai.net/">Towards AI</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Customer Segmentation using K-Means Clustering]]></title>
            <link>https://medium.com/swlh/customer-segmentation-using-k-means-clustering-f440566bdc67?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/f440566bdc67</guid>
            <category><![CDATA[rfm-analysis]]></category>
            <category><![CDATA[k-means-clustering]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[unsupervised-learning]]></category>
            <category><![CDATA[customer-segmentation]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Wed, 11 May 2022 19:01:25 GMT</pubDate>
            <atom:updated>2022-05-11T19:01:25.716Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>Learn and implement k-means algorithm in customer segmentation in less than 5 minutes</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TEsbk5VMw2x2JbHHEO21zw.png" /></figure><p><strong>Simple and short definition: </strong>“Identify similarity among customers based on different attributes and group them together”</p><p>Next, few essential notes on customer segmentation is provided followed by the python code.</p><h3>Types of customer segmentation</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*U88pxUjqyM-WtRQZy0sdZg.png" /><figcaption>Types of customer segmentation approaches</figcaption></figure><h3>RBC of Customer Segmentation</h3><p><strong>Reason</strong></p><ul><li>Failure to understand target audience</li><li>Ineffective marketing campaign, marketing and product mix</li><li>Limited resource and non-optimised cost allocation</li><li>Lack of activity prioritisation</li><li>Lack of guidance in product development resulting in longer time-to-market</li></ul><p><strong>Benefits</strong></p><ul><li>Better understand target audience by improved order fulfilment</li><li>Improved customer response, high customer engagement, loyalty and retention, better brand visibility</li><li>Explore and grab new business opportunities</li><li>Improves customer lifetime value, optimises sales funnel</li></ul><p><strong>Cautions</strong></p><ul><li>Segments must align with business goals and context</li><li>Lack of quality data and volume can lead to inferior segments</li><li>Segment performance must be monitored over time for any drift from expectations</li></ul><h3>Python code for Segmentation using K-Means Clustering</h3><h4>Import necessary python libraries</h4><p>Import all necessary libraries and update necessary notebook properties</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/84104277717ceaed8d4ba1ac3711ef67/href">https://medium.com/media/84104277717ceaed8d4ba1ac3711ef67/href</a></iframe><h4>Compute Recency, Frequency, Monetary values</h4><p>Three features are critical for feature engineering, which are as follows:</p><ol><li><strong>Recency </strong>— Days since last purchase w.r.to specific customer</li><li><strong>Frequency</strong> — Number of purchase over a specified time w.r.to specific customer</li><li><strong>Monetary</strong> — Total monetary contribution w.r.to specific customer</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cdf74627d8221324447446571e9ca316/href">https://medium.com/media/cdf74627d8221324447446571e9ca316/href</a></iframe><h4>Re-Scale Data using Normalisation</h4><p>Since, a distance based algorithm will be used as a modelling approach, all data columns must be scaled adequately. In this case, the data is scaled using min-max method within [0, 1]. However, other methods such as normalisation can also be used.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d28e17adf27614bdafdc28a0be839141/href">https://medium.com/media/d28e17adf27614bdafdc28a0be839141/href</a></iframe><h4>Group customer segments using K-Means clustering</h4><p>Given, the problem has no label data, an unsupervised algorithm is chosen. In this case, a k-means algorithm is chosen which is a popular distance based algorithm. K-means algorithm provides significantly good results within reasonable time and cost. Algorithms such as hierarchical algorithm is considered as a good alternative.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/47bb517aa986ad00077c9698f08379b7/href">https://medium.com/media/47bb517aa986ad00077c9698f08379b7/href</a></iframe><h4>Visualise R-F-M distribution based on K-Means cluster</h4><p>The distribution of recency, frequency and monetary values across multiple clusters should be visualised to provide clarity and drift of segments over time. It enables to develop necessary strategies to counter any unexpected behaviours.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d75ce07cf2e1d17ba5c0965d05dad0fa/href">https://medium.com/media/d75ce07cf2e1d17ba5c0965d05dad0fa/href</a></iframe><h3>Conclusion</h3><p>Based on the results obtained, i.e. customer segments, tailored recommendations can be provided to the consumers that improves the ability to fulfil customer expectations. Therefore, it is quite crucial for every organisation to analyse customer segments occasionally and roll out different marketing campaigns and promotions.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f440566bdc67" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/customer-segmentation-using-k-means-clustering-f440566bdc67">Customer Segmentation using K-Means Clustering</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Feature Selection — Using Genetic Algorithm]]></title>
            <link>https://medium.com/analytics-vidhya/feature-selection-using-genetic-algorithm-20078be41d16?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/20078be41d16</guid>
            <category><![CDATA[feature-selection]]></category>
            <category><![CDATA[logistic-regression]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Mon, 20 Jul 2020 07:44:53 GMT</pubDate>
            <atom:updated>2020-11-26T07:03:25.344Z</atom:updated>
            <cc:license>http://creativecommons.org/licenses/by/4.0/</cc:license>
            <content:encoded><![CDATA[<h3>Feature Selection — Using Genetic Algorithm</h3><p>Let’s combine the power of Prescriptive and Predictive Analytics</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/760/1*gGcDYTbs_y6NQdgjr1lYXg.jpeg" /><figcaption>Source: analyticsvidhya.com</figcaption></figure><p>All Machine Learning models use a large volume of data to train to predict the patterns in the future. It implies that the machine learning models are susceptible to the quality of data. Even with minute errors, the models may train to yield infeasible or inferior results. Thus, the quality of data used for training is the utmost concern of an organization.</p><p>In this direction, feature selection plays a crucial role. Different techniques are present such as <strong>forwards selection</strong>, <strong>backward elimination</strong>,<strong> stepwise selection</strong>, etc. to select a feature set. However, most of these approaches are performed manually and are computationally expensive and time-consuming. Therefore, in this article, the Genetic Algorithm is used to obtain an optimal feature within a reasonable amount of time.</p><p>The structure of this article is as follows.</p><ul><li><strong>Feature Selection</strong> — What is it? And why do we need it?</li><li><strong>Genetic Algorithm</strong> — What is it? And why do we need it?</li><li><strong>Genetic Algorithm</strong><em> in</em><strong><em> </em>Feature Selection</strong> — How to do it?</li></ul><h3>Feature Selection: Lets cut the clutter</h3><p><strong>Feature Selection</strong> is the process in <strong>Data Wrangling,</strong> where certain features that contribute most to the <strong>Target Variable </strong>are selected. Learning from irrelevant features in the data can decrease the <strong>Accuracy</strong> and <strong>Performance</strong> of the model.</p><p>The most common way to remove irrelevant features is through <strong>Univariate Selection</strong>, by <strong>Feature Importance</strong> and using <strong>Correlation Matrix</strong>. This article provides an excellent overview of <a href="https://towardsdatascience.com/feature-selection-techniques-in-machine-learning-with-python-f24e7da3f36e#:~:text=Feature%20Selection%20is%20the%20process,learn%20based%20on%20irrelevant%20features.">feature selection</a>.</p><p>To proceed with feature selection, certain preprocessing steps such as <strong>missing value imputation</strong>, <strong>removing outliers</strong>, <strong>dropping irrelevant features</strong>, identifying the feature set, and the target variable.</p><p>The python code to preprocess data is provided below using the dataset <a href="https://www.kaggle.com/ronitf/heart-disease-uci">Heart Disease Dataset</a>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/17e19d85a93197ff75a0cad3631ccf9f/href">https://medium.com/media/17e19d85a93197ff75a0cad3631ccf9f/href</a></iframe><h3>Genetic Algorithm: The popular meta-heuristics</h3><p><strong>Genetic Algorithm</strong> (GA) is one of the most popular <a href="https://en.wikipedia.org/wiki/Evolutionary_algorithm">Evolutionary Algorithms</a> (EA) used by experts from academia and industry. GA uses three operators: <strong>selection, </strong><a href="https://medium.com/@samiranbera_66038/crossover-operator-the-heart-of-genetic-algorithm-6c0fdcb405c0"><strong>crossover</strong></a><strong> </strong>&amp;<strong> </strong><a href="https://medium.com/analytics-vidhya/mutation-break-free-from-stagnation-e31473a50015"><strong>mutation</strong></a><strong> </strong>to improve the quality of solutions. This <a href="https://medium.com/swlh/transportation-problem-solve-using-genetic-algorithm-77186e5fdecf">article</a> provides a clear understanding of GA and how to implement operators on a <strong>Transportation Problem</strong>.</p><p>The Genetic Algorithm can be used in several kinds of problems with very little modification, thus provides development flexibility at a very low cost. Further, the Genetic Algorithm has fewer constraints (such as <strong>parameter tuning</strong>) compared to other meta-heuristics techniques and thus can obtain an optimal solution efficiently. The python code for basic Genetic Algorithm operators is provided below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a30327ffe9115c30d88b60324d6c10e9/href">https://medium.com/media/a30327ffe9115c30d88b60324d6c10e9/href</a></iframe><h3>Genetic Algorithm for Feature Selection</h3><p>To implement the Genetic Algorithm for Feature Selection, the accuracy of the predictive model is considered as the fitness of the solution, where the accuracy of the model is obtained by using the Logistic Regression.</p><p>For each chromosome, the predictive_model() function evaluates the accuracy score, which is aggregated at get_fitness() function for the entire population. The python code for the fitness function of the predictive model is provided below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d65a4861912166b45c54d52ef4bd62a4/href">https://medium.com/media/d65a4861912166b45c54d52ef4bd62a4/href</a></iframe><p>The main program is executed using the ga() function. This function takes a list of the following arguments:</p><ul><li>data: The dataset used in the study</li><li>feature_list: Aset of features which need to be optimized</li><li>target: Denotes the dependent variable</li><li>n: The size of the population</li><li>max_iter: The number of iterations to evaluate</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/079c92f1bfe1f81c5a15df6abf377bd8/href">https://medium.com/media/079c92f1bfe1f81c5a15df6abf377bd8/href</a></iframe><p>The function returns the optimal setting of feature selection as a binary array with the best accuracy score.</p><h3>The Big Bonus</h3><p>Executing the above program will produce an optimal set of features. However, it is interesting to observe that more than one optimal feature set can be present, i.e., a problem with <strong>Multiple-Optimal solutions</strong>. This can be observed from the outputs obtained by executing the following code.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d87e68b6332220c5e63f529aae90dff0/href">https://medium.com/media/d87e68b6332220c5e63f529aae90dff0/href</a></iframe><p>In the first output, seven features were selected, which provides the optimal accuracy score of 90%.</p><pre><strong>OUTPUT 1:</strong><br>Optimal Feature Set<br> [&#39;thalach&#39;, &#39;cp_4&#39;, &#39;restecg_1&#39;, &#39;exang_1&#39;, &#39;ca_2&#39;, &#39;thal_6&#39;, &#39;thal_7&#39;]</pre><pre>Optimal Accuracy = 90.0 %</pre><p>And in the second output, twelve features were selected, which provides the optimal accuracy score of 90%.</p><pre><strong>OUTPUT 2:</strong><br>Optimal Feature Set<br> [&#39;Age&#39;, &#39;chol&#39;, &#39;oldpeak&#39;, &#39;Sex_1&#39;, &#39;cp_4&#39;, &#39;fbs_1&#39;, &#39;restecg_2&#39;, &#39;exang_1&#39;, &#39;slope_3&#39;, &#39;ca_1&#39;, &#39;thal_6&#39;, &#39;thal_7&#39;]</pre><pre>Optimal Accuracy = 90.0 %</pre><p>Both feature set gives an accuracy of 90%. Thus either one can be used. But, the selection of a feature set combination also requires knowledge and experience in the business process. Thus, even with the help of the Genetic Algorithm to filter the best feature set, it is always good to make decisions based on business objectives rather than simply building a high accuracy model.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=20078be41d16" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/feature-selection-using-genetic-algorithm-20078be41d16">Feature Selection — Using Genetic Algorithm</a> was originally published in <a href="https://medium.com/analytics-vidhya">Analytics Vidhya</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Formulate Vehicle Routing Problem— Using GAMS]]></title>
            <link>https://medium.com/swlh/formulate-vehicle-routing-problem-using-gams-462afedfe98?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/462afedfe98</guid>
            <category><![CDATA[vehicle-routing-problem]]></category>
            <category><![CDATA[prescriptive-analytics]]></category>
            <category><![CDATA[mathematical-modeling]]></category>
            <category><![CDATA[gam]]></category>
            <category><![CDATA[operations-research]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Sun, 21 Jun 2020 21:00:12 GMT</pubDate>
            <atom:updated>2020-06-23T06:49:21.769Z</atom:updated>
            <content:encoded><![CDATA[<p>Solve Small-Scale Vehicle Routing Problem</p><p><a href="https://en.wikipedia.org/wiki/Vehicle_routing_problem#:~:text=The%20vehicle%20routing%20problem%20(VRP,given%20set%20of%20customers%3F%22.&amp;text=The%20objective%20of%20the%20VRP%20is%20to%20minimize%20the%20total%20route%20cost.">Vehicle Routing Problem (VRP)</a> is a combinatorial problem that determines the optimal path for vehicles to deliver goods from source to destination minimizing cost. Thus, it is formulated as a <a href="http://egon.cheme.cmu.edu/ewo/docs/EWOMINLPGrossmann.pdf">Mixed Integer Non-Linear Programming (MINLP)</a> problem with a minimizing Objective function.</p><p>VRP generalizes the <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem#:~:text=The%20travelling%20salesman%20problem%20(also,returns%20to%20the%20origin%20city%3F%22">Travelling Salesman Problem (TSP)</a>.</p><p><strong>Problem Description:</strong> Consider a network with <em>N=6</em> nodes with <em>E=10 </em>edges connection these nodes as shown below. The goal is to find the path with the lowest cost connecting nodes <em>A </em>and <em>F </em>without making any sub-tours.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*C97soP8z1Ah9fgQnNDMZkw.png" /><figcaption>Routing Network Diagram</figcaption></figure><p><strong>Solution:</strong> There are 16 possible paths that connect node <em>A</em> and <em>F </em>in the above diagram<em>,</em> which are A-B-C-F, A-B-C-E-F, A-B-C-D-E-F, A-B-D-C-F, A-B-D-C-E-F<br>A-B-D-E-F, A-C-F, A-C-E-F, A-C-D-E-F, A-C-B-D-E-F, A-D-B-C-F, A-D-B-C-E-F, A-D-C-F, A-D-C-E-F, A-D-E-C-F, and A-D-E-F. The optimal path is A-D-E-F with total cost = 4.</p><h3>Mathematical Formulation:</h3><p>The VRP formulation is provided into 2 segments:</p><ul><li>Single Source — Single Destination Problem</li><li>Multiple Source — Multiple Destination Problem</li></ul><h4>Single Source — Single Destination Problem</h4><p>A Vehicle Routing Problem where goods are delivered from a single destination to a single destination is termed as a single source-single destination problem. The mathematical formulation to the MINLP Problem is given below,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/435/1*x4mTlt3zIZ1gzlXS8X7BAQ.png" /></figure><p>Equation 1 represents the objective function that computes the total cost to deliver goods from source to destination via an optimal path. Equation 2 ensures that the incoming and outgoing edges are different for each node. Equation 3 and 4 initiates and concludes the optimal path at source <em>(S) </em>and destination <em>(N) </em>nodes respectively. Equation 5 ensures that the number of incoming and outgoing edges from a node are equal, which in this case is equal to 1. Equation 6 and 7 eliminate any sub-tours using variable <em>T </em>which computes the delivery cost and binary variable <em>X</em> which<em> </em>is equal to 1 if goods are delivered from node <em>i </em>to node <em>j, </em>or 0 otherwise. Finally, equation 8 ensures that the variable <em>X</em> is binary.</p><p><strong>Note:</strong> Equation 7 is non-linear, but can be linearized using Big-M constraints as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/1*2cuXv_DCeBoOoTCPhnPGvg.png" /></figure><h4>Multiple Source — Multiple Destination Problem</h4><p>A Vehicle Routing Problem where goods are delivered from multiple sources to multiple destinations is termed as a multiple source-multiple-destination problem. It can be considered as an extension to the single source single destination problem, where each source-destination combination is considered as a new route <em>(r).</em></p><p>The mathematical formulation to the MINLP Problem is given below,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/450/1*abQ__AINJbXh61bx04ciyg.png" /></figure><p>Equation 1 represents the objective function that computes the total cost to deliver goods from multiple sources to multiple destinations via optimal paths. Equation 2 ensures that the incoming and outgoing edges are different for each node and route. Equation 3 and 4 initiates and concludes the optimal path at multiple sources <em>(Sr) </em>and multiple destinations <em>(Nr) </em>nodes for all routes respectively. Equation 5 ensures that the number of incoming and outgoing edges from a node are equal, which in this case is equal to 1 for all routes. Equation 6 and 7 eliminate any sub-tours for routes <em>r </em>using variable <em>T </em>which computes the delivery cost and binary variable <em>X</em> which<em> </em>is equal to 1 if goods are delivered from node <em>i </em>to node <em>j, </em>or 0 otherwise. Finally, equation 8 ensures that the variable <em>X</em> is binary.</p><p><strong>Note:</strong> Equation 7 is non-linear, but can be linearized using Big-M constraints as explained above.</p><p>It can be seen that each source-destination combination has a separate route. However, in reality, more than one destination can be served on a single route. It implies that one or more than one destination can be an intermediate node. This characteristic is not captured in the above problem for the sake of simplicity.</p><h3>Let&#39;s run on GAMS</h3><p><a href="https://en.wikipedia.org/wiki/General_Algebraic_Modeling_System">GAMS</a> or General Algebraic Modeling System is a software to model and solve optimization problems. To obtain GAMS, visit <a href="https://www.gams.com/download/">here</a>. Follow chapter 2 from the GAMS user manual to start modeling in GAMS.</p><p>The mathematical model in the GAMS environment for a single-source single destination and multiple-source multiple destinations is provided <a href="https://gist.github.com/samiranberahaldia/e837b24f72f5bd4fb0e108c1beb07ff9">here </a>and <a href="https://gist.github.com/samiranberahaldia/86a0d6f0e9df7fd2d22bf5b27fe8ad80">here</a> respectively. Execute the models in the GAMS environment to see results provided next.</p><p><strong>GAMS code for Single source — Single destination Vehicle Routing Problem:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/faa7c94258c06fd736f8afeb7a20df07/href">https://medium.com/media/faa7c94258c06fd736f8afeb7a20df07/href</a></iframe><p><strong>GAMS code for Multiple sources — Multiple destination Vehicle Routing Problem:</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/70dc595472ea26628b04064e16a2616f/href">https://medium.com/media/70dc595472ea26628b04064e16a2616f/href</a></iframe><p><em>Numerical Example:</em> Generate<em> </em>the small size transportation cost matrix for <em>N=5</em> nodes with <em>E=20</em> edges.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/367/1*ybOo59orXHp5F_jwjagn7g.png" /><figcaption>Transportation Cost Matrix</figcaption></figure><ul><li>By solving the single source — single destination problem, the optimal path obtained is 1–2–3–5 having total cost = 13.</li><li>By saving the multiple source — multiple destination problem, the optimal paths obtained are Route 1: 1–2–3–5 and Route 2: 3–1–2 having total cost=22.</li></ul><h3>The Concluding Note</h3><p>Routing problems are very popular among academic and research communities. And searching <a href="http://scholar.google.com/">Google Scholar</a>, it can be found that a vast pool of variants and solution techniques has been developed over the decades. Thus, routing problems are rising a cliff very steep.</p><p>In this article, a small problem is taken into account to explain the mathematical model of a routing problem. To execute a large size problem, commercial solvers cannot be used due to resource constraints. To this end, switching up to heuristics/meta-heuristic such as the Genetic Algorithm, Particle Swarm Intelligence, Grey Wolf Optimizer, and many others can prove to be useful.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=462afedfe98" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/formulate-vehicle-routing-problem-using-gams-462afedfe98">Formulate Vehicle Routing Problem— Using GAMS</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Mutation — Break Free from Stagnation]]></title>
            <link>https://medium.com/analytics-vidhya/mutation-break-free-from-stagnation-e31473a50015?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/e31473a50015</guid>
            <category><![CDATA[mutation]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[mutation-rate]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Sat, 20 Jun 2020 03:24:16 GMT</pubDate>
            <atom:updated>2020-06-20T16:19:23.624Z</atom:updated>
            <content:encoded><![CDATA[<h3>Mutation — Break Free from Stagnation</h3><p>Learn how to implement Mutation Operator in Python</p><p>Mutation Operator is a popular technique used in the <a href="https://en.wikipedia.org/wiki/Genetic_algorithm">Genetic Algorithm</a>. However, it has found its way to other <a href="https://en.wikipedia.org/wiki/Heuristic">Heuristic</a> and <a href="https://en.wikipedia.org/wiki/Metaheuristic">Meta-Heuristic</a> techniques through hybridization. It is primarily due to its ability to escape local optima and explore a wider solution space.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*hWH4fwICupDWRq5SZZSB0w.png" /></figure><p>This article briefly discusses some of the popular mutation operators used today for optimization along with <a href="https://en.wikipedia.org/wiki/Python_(programming_language)">python</a> codes.</p><h3><strong>The Operators:</strong></h3><p><strong>Random Mutation:</strong> Genes from a Chromosome is modified at one or more position based on random numbers. Here <em>‘x’</em> represents a chromosome of a single dimension and ‘<em>a’</em> is the number to be replaced at random positions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7a2f17c5f9a658838d9c9066242384ad/href">https://medium.com/media/7a2f17c5f9a658838d9c9066242384ad/href</a></iframe><p><strong>Flip Mutation:</strong> Genes from a Chromosome is modified at all position based on the maximum values of all genes. For a binary chromosome, the maximum value is set to 1.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/31fdf1d3a4365cca30cc82f36c0d6ec3/href">https://medium.com/media/31fdf1d3a4365cca30cc82f36c0d6ec3/href</a></iframe><p><strong>Bit-String Mutation:</strong> It is a variant of Flip Mutation, where gene modification is determined based on the random numbers for one or more positions.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ee2036689184f4f12585d4694f4f9202/href">https://medium.com/media/ee2036689184f4f12585d4694f4f9202/href</a></iframe><p><strong>Boundary Mutation:</strong> Genes from a Chromosome is modified if their value either drops below the lower bound <em>(LB)</em>or exceed the upper bound <em>(UB) </em>specified.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e11f91fa2b0c96d18888b2c7b26bf64/href">https://medium.com/media/6e11f91fa2b0c96d18888b2c7b26bf64/href</a></iframe><p><strong>Swap Mutation:</strong> Two Genes from a Chromosome exchange their position, i.e. swap values of genes. Here ‘<em>a’</em> and ‘<em>b’</em> represents two positions at which genes are exchanged.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fd99603dc5f8f94f853506c0256f4623/href">https://medium.com/media/fd99603dc5f8f94f853506c0256f4623/href</a></iframe><p><strong>Inverse Mutation:</strong> It is a variant of Swap Mutation. Genes positioned at an equal distance across the center of a Chromosome are swapped, thereby reversing the chromosome.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d9f201b91a9ee25e7b232e239c2906b2/href">https://medium.com/media/d9f201b91a9ee25e7b232e239c2906b2/href</a></iframe><p><strong>Insert Mutation: </strong>A Gene of a chromosome is cropped from one position and inserted at another position. However, more than one gene can also be cropped at multiple positions and inserted at another position. Here ‘<em>a’</em> represents the position where the gene is cropped from and ‘<em>b’</em> represents the position where it is inserted.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5ae107dfb73957ca87688224f015640c/href">https://medium.com/media/5ae107dfb73957ca87688224f015640c/href</a></iframe><p><strong>Shift Mutation: </strong>One or more than one Gene of a chromosome is modified by shifting the genes either to the left or right by ‘<em>n’</em> times.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d38cec182242c047119f16f9de98226/href">https://medium.com/media/6d38cec182242c047119f16f9de98226/href</a></iframe><p><strong>Increment or Decrement Mutation:</strong> Genes of a Chromosome are modified either by increasing or decreasing the values using ratio. The ratio <em>(r) </em>is generated randomly and lies within the range [0,1].</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2eb5f1ed69fafc0c3e15613aa6e8ea3e/href">https://medium.com/media/2eb5f1ed69fafc0c3e15613aa6e8ea3e/href</a></iframe><p><strong>The Concluding Note</strong></p><p>The Mutation operator adds diversity to the population. Thus it is essential, as it allows search algorithms like the <a href="https://en.wikipedia.org/wiki/Genetic_algorithm">Genetic Algorithm</a> to escape from local optima by promoting exploration. This article provides many mutation operators, however, the list above is not exhaustive. More mutation operators are developed each day and can be found on <a href="http://scholar.google.com/">Google Scholar</a>.</p><p>This article would be incomplete without answering these frequently asked questions on social networks.</p><p><em>Q1: Which mutation operator should I use?</em></p><p>Well, that depends on the problem. However, random mutation, flip mutation, and increment/decrement operators is a good place to start.</p><p><em>Q2: Should I use only one mutation operator?</em></p><p>Well, there is no such rule. One or more than one mutation operator can be used together in combination.</p><p><em>Q3: How frequently should mutation be done?</em></p><p>The mutation rate depends on the problem. But, it is usually quite low around 30% or less. It is because a search algorithm with a high mutation rate behaves like a <a href="https://en.wikipedia.org/wiki/Random_search">random search</a> and thus isn’t much reliable.</p><p>I hope you liked this article.</p><p>Image source: <a href="https://www.nature.com/articles/d41586-019-03536-x">https://www.nature.com/articles/d41586-019-03536-x</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e31473a50015" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/mutation-break-free-from-stagnation-e31473a50015">Mutation — Break Free from Stagnation</a> was originally published in <a href="https://medium.com/analytics-vidhya">Analytics Vidhya</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Transportation Problem — Solve using Genetic Algorithm]]></title>
            <link>https://medium.com/swlh/transportation-problem-solve-using-genetic-algorithm-77186e5fdecf?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/77186e5fdecf</guid>
            <category><![CDATA[transportation-problem]]></category>
            <category><![CDATA[mathematical-modeling]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Fri, 19 Jun 2020 13:23:04 GMT</pubDate>
            <atom:updated>2020-06-21T16:28:45.155Z</atom:updated>
            <content:encoded><![CDATA[<h3>Transportation Problem — Solve using Genetic Algorithm</h3><p>Quick and simple implementation using Python</p><p><a href="https://en.wikibooks.org/wiki/Operations_Research/Transportation_and_Assignment_Problem">Transportation problem (TP)</a> is one of the most popular problems in <a href="https://en.wikipedia.org/wiki/Operations_research">Operations</a>. However, people from other areas have also shown interest to learn the formulation and solution techniques for TP. It is because it can be related to a wide variety of problems and thus acts as a stepping stone for model development.</p><p>This article is structured into three segments:</p><ul><li>Introduction to Transportation Problem</li><li>Genetic Algorithm and its Operators</li><li>Implementing Genetic Algorithm to Transportation Problem</li></ul><h3><strong>1.0 Introduction to Transportation Problem</strong></h3><p>Transportation Problem is a combinatorial problem that deals with transporting items from multiple sources to multiple destinations at minimum cost. The transportation problem is formulated as a <a href="https://www.gurobi.com/resource/mip-basics/">Mixed-Integer Programming (MIP)</a> problem where the objective function is minimization.</p><p>The mathematical formulation of the Transportation Problem is given below,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/341/1*japsrDmPELZP8jaskEnBEQ.png" /></figure><p>where,</p><ul><li>c is the cost to travel from source <em>i </em>to destination <em>j</em></li><li>x is a binary variable that connects source <em>i</em> to destination <em>j</em></li></ul><p>As seen above, equation (1) is the objective function that tries to minimize the total cost of transporting from sources <em>i</em> to destination <em>j</em>, equation (2) and (3) restricts transportation from each node to only one destination and vice-versa. It can be observed that items can be transported from one or more sources to one or more destinations by modifying equations (2–3). However, it is not in the scope of this article. And finally, equation (4) is the binary constraints.</p><p><strong>Numerical Illustration: </strong>Using <a href="https://en.wikipedia.org/wiki/Brute-force_search">Exhaustive or Brute Force Search</a></p><p>Consider a Transportation Problem with 3 sources — A, B, C, and 3 destinations — D, E, F. An <a href="https://en.wikipedia.org/wiki/Brute-force_search">Exhaustive Search or Brute Force Search</a> technique to solve the Transportation Problem comprises of three 3 simple steps,</p><ul><li>Step 1: Find all possible source-destination combinations — (AD, BE, CF), (AD, BF, CE), (AE, BD, CF), (AE, BF, CD), (AF, BD, CE) and (AF, BE, CD)</li><li>Step 2: Calculate the cost of each combination. Assume $23, $56, $12, $53, $18, and $54 to be the transportation cost for the above combinations respectively</li><li>Step 3: Select a combination with the minimum cost as the optimal solution which is (AE, BD, CF) with transportation cost = $12.</li></ul><h4><strong>The Need for Heuristics/Meta-Heuristics</strong></h4><p>Solving small scale Transportation problems is quite simple and fast as seen above. However, with an increase in the number of sources and destinations, the Transportation Problem becomes computationally difficult to solve within a reasonable amount of time. It is due to an exponential increase in source-destination combination. Therefore, a <a href="https://en.wikipedia.org/wiki/Metaheuristic">heuristic/meta-heuristics technique </a>such as a <a href="https://en.wikipedia.org/wiki/Genetic_algorithm">Genetic Algorithm</a> can be used to obtain the optimal solution in lesser time.</p><h3>2.0 Genetic Algorithm and its Operators</h3><p>Genetic Algorithm (GA) is one of the most popular <a href="https://en.wikipedia.org/wiki/Evolutionary_algorithm">Evolutionary Algorithms</a> used by people from academia and industry. It comprises of three operators: <strong>selection, crossover </strong>&amp;<strong> mutation</strong>. Many literatures on this subject can be found on <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C5&amp;q=Genetic+Algorithm&amp;btnG=">Google Scholar</a>.</p><p><strong>2.1. Key Components of the Genetic Algorithm:</strong></p><ul><li><em>Chromosome:</em> A combination of 0–1 for the binary variable (x)</li><li><em>Population:</em> A set of chromosomes</li><li><em>Parents: </em>Present set of chromosomes</li><li><em>Children</em>: Set of chromosome derived from Parents</li><li><em>Fitness:</em> The objective function value of a chromosome</li></ul><h4><strong>2.2 Genetic Algorithm Operators:</strong></h4><p>In this article, the primary focus is simply implementing GA with the following operators: <em>Random Selection Operator, Single Point Crossover Operator, </em>and <em>Shift Mutation Operator.</em></p><p><strong>2.2.1 Random Selection:</strong> The chromosomes from the population are selected in a random fashion to form children. The algorithm of random selection is quite simple and easy to implement. The python code of the Random Selection operator is provided below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/93e5a5bf999a65ef2c1f806b0baed29a/href">https://medium.com/media/93e5a5bf999a65ef2c1f806b0baed29a/href</a></iframe><p>It should be noted that the selection of chromosomes may be sub-optimal. To this end, other selection operators such as Tournament Selection, Roulette Wheel selection, etc can be used as well.</p><p><strong>2.2.2 Single Point Crossover: </strong>In a single-point crossover, a <strong>crossover point</strong> is randomly generated which determines the point for the exchange of information between parents to form children. The python code of single point crossover operator is provided below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e3a8d2e62bad5455f3fde2efee11e246/href">https://medium.com/media/e3a8d2e62bad5455f3fde2efee11e246/href</a></iframe><p>For example, when the crossover point generated is 2, all information from index 3 onwards are exchanged between the two parents to form children, as described <a href="https://medium.com/@samiranbera_66038/crossover-operator-the-heart-of-genetic-algorithm-6c0fdcb405c0">here</a>.</p><p><strong>2.2.3 Shift Mutation:</strong> The chromosome from the population is modified by using either the left or right shift. The number of positions a chromosome shift is generated randomly. The python code of shift mutation operator is provided below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3f4be396acb606c39bbc7a1f11bca56a/href">https://medium.com/media/3f4be396acb606c39bbc7a1f11bca56a/href</a></iframe><p>Using mutation, GA can escape local optima (i.e. stagnation) and explore solution space more efficiently. However, the mutation rate needs to low, which otherwise makes GA behave like a random search.</p><h3>3.0 Implementing Genetic Algorithm to Transportation Problem</h3><p>To execute the Genetic Algorithm, an initial population is generated as an initial feasible solution, which is encoded and decoded based on the problem. These solutions are improved to obtain an optimal solution iteratively. Next, a brief overview of population initialization, encoding, and the fitness function is given, followed by the main program.</p><ul><li><em>Initialize Population:</em> The population of chromosomes is generated randomly with range[0, 1] with <em>N</em> rows and <em>C</em> columns, where <em>M</em> is the number of chromosomes and <em>C</em> is the length of chromosome/number of source or destination nodes.</li><li><em>Encoding Chromosome:</em> Fractional numbers are ranked starting from 0. Therefore, an array [0.47, 0.99, 0.88, 0.18, 0.85] is modified to [1, 4, 3, 0, 2].</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/05edd80ba636ef27ada62b0632059d1e/href">https://medium.com/media/05edd80ba636ef27ada62b0632059d1e/href</a></iframe><p><em>Fitness of a Chromosome: </em>The performance of a chromosome in a population is measured by computing the objective function value, i.e. summing the product of cost (c) and binary matrix (x).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d56f28f7910f3e43de7be54a61020e25/href">https://medium.com/media/d56f28f7910f3e43de7be54a61020e25/href</a></iframe><p>The main program of the Genetic Algorithm given below integrates all operators and functions discussed above. To obtain an optimal solution, pass the transportation cost matrix as an argument.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6a35dac7448489c2023acfb25d5afe25/href">https://medium.com/media/6a35dac7448489c2023acfb25d5afe25/href</a></iframe><p><em>The output from the program:</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/db75763a13d24c8445eb9f2063b7a9d5/href">https://medium.com/media/db75763a13d24c8445eb9f2063b7a9d5/href</a></iframe><p><strong>Finally, You made it to the end!</strong></p><p>First of all, thank you for going through the entire article. I know it isn’t easy to follow such a long article. I wish that I could have written it short, but that would defeat the purpose of learning. The complete code in python is available <a href="https://github.com/samiranberahaldia/Transporation_Problem_using_Genetic_Algorithm/blob/master/Transportation_GA.ipynb">here</a>.</p><p>So, from this article, you know how to implement the Genetic Algorithm to a Transportation Problem in a simple manner. And now you can experiment and modify the Genetic Algorithm operators or use Genetic Algorithm to solve other combinatorial problems.</p><p>Please note, there are few other ways to apply the Genetic Algorithm to a Transportation Problem. In fact, everyone has their own way of implementing. So, expand the search and try to implement it with the help of a problem.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=77186e5fdecf" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/transportation-problem-solve-using-genetic-algorithm-77186e5fdecf">Transportation Problem — Solve using Genetic Algorithm</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Crossover Operator — The Heart of Genetic Algorithm]]></title>
            <link>https://medium.com/swlh/crossover-operator-the-heart-of-genetic-algorithm-6c0fdcb405c0?source=rss-99b9ef3643e------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c0fdcb405c0</guid>
            <category><![CDATA[crossover]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[python3]]></category>
            <dc:creator><![CDATA[Dr.  Samiran Bera (PhD)]]></dc:creator>
            <pubDate>Fri, 15 May 2020 13:42:57 GMT</pubDate>
            <atom:updated>2020-05-15T13:42:57.726Z</atom:updated>
            <content:encoded><![CDATA[<h3>Crossover Operator — The Heart of Genetic Algorithm</h3><p>Learn how to implement a crossover operator in python</p><p>History of the Genetic Algorithm (GA) dates back to the 1960s, and since then people around the world have used it to solve <strong>search and optimization</strong> problems. It is because the Genetic Algorithm is pretty easy to learn and has a faster rate of deployment. Therefore, the Genetic Algorithm has become one of the most popular algorithms for people from academics and industry.</p><p>Genetic Algorithm composes of three operators: <strong>Selection</strong>,<strong> Crossover</strong>, and <strong>Mutation</strong>. Each operator has its own role to play and is equally important. However, in this article, the focus is on the <strong>Crossover Operators</strong> and how to implement it in <strong>python</strong> with a simple example.</p><p>So, let&#39;s begin with the three most popular crossover operators.</p><h4><strong>Single Point Crossover Operator</strong></h4><blockquote>“Information exchange at a single point”</blockquote><p>In a single-point crossover, a <strong>crossover point</strong> is randomly generated which determines the point for exchange of information between parents to form children. For example, when the crossover point generated is 2, all information from index 3 onwards are exchanged between the two parents to form children, as shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*BIwSv7IaHf0Ab9xluOlvxg.png" /><figcaption>Single Point Crossover</figcaption></figure><p>To implement the single-point crossover, the following python code can be used. A <em>single_point_crossover</em> function is defined where arguments A &amp; B represent the parents, x denotes the crossover point, and A_new &amp; B_new represent the children.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*7l49YuJXSVaum3SWOjVmlQ.png" /><figcaption>Python Code: Single Point Crossover Operator</figcaption></figure><h4><strong>Multi-Point Crossover Operator</strong></h4><blockquote>“Information exchange at multiple points”</blockquote><p>In a multi-point crossover, <strong>multiple crossover points</strong> are randomly generated which determines the points for exchange of information between parents to form children. This results in the <strong>exchange of information between the crossover points</strong>.</p><p>To understand this in a simple fashion, consider 2 crossover points 2 &amp; 6. And then perform single-point crossover at crossover points 2 &amp; 6 sequentially on the parents to form children. Thus, a two-point crossover can simply be considered as a single-point crossover executed over two different crossover points.</p><p><em>Note: A two-point crossover is a multi-point crossover technique with two crossover points</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/498/1*mGa08Jki1bOdHLUIldQr3A.png" /><figcaption>Two-Point or Multi-point Crossover</figcaption></figure><p>To implement the two-point crossover, the following python code can be used. A <em>multi_point_crossover</em> function is defined where incoming arguments A &amp; B represent the parents, X denotes an array of crossover points, and returning A &amp; B represent the children. It can be observed that for each crossover point in X, <em>single_point_crossover </em>operation is performed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/1*gp6LoiZgyzOuYF7IZmd9JQ.png" /><figcaption>Python Code: Multipoint Crossover Operator</figcaption></figure><h4><strong>Uniform Crossover Operator</strong></h4><blockquote>“Information exchange based on probability”</blockquote><p>In the uniform crossover, information exchange between parents takes place based on some probability values. A probability matrix of length same as the parents is randomly generated. If the probability value exceeds a predefined threshold at one or more index, information is exchanged at those indexes between parents to form children.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*UcEr_O8oGETctZO35AdeXg.png" /><figcaption>Uniform Crossover</figcaption></figure><p>To implement the uniform crossover, the following python code can be used. A <em>uniform_crossover</em> function is defined where incoming arguments A &amp; B represent the parents, P denotes the probability matrix, and returning A &amp; B represent the children. It can be observed that the information between parents is exchanged at the indexes where probability is less than the threshold (0.5) to form children.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*jX0x1w7GA1q3NI32e3rw9Q.png" /><figcaption>Python Code: Uniform Crossover Operator</figcaption></figure><p><em>Note: Threshold values less or greater than 0.5 can be considered</em></p><h4>BONUS: Other Crossover Operators across the Aisle</h4><p>Besides these, there are many several other crossover techniques such as partially mapped crossover (PMX), cycle crossover (CX), order crossover (OX), etc. These techniques are much more complex compared to a single point and multi-point crossover technique.</p><h3>Verdict!</h3><p>So which one should one choose? Frankly, it depends on the problem you choose and the result you get. Usually, most people start with single-point crossover and move to multi-point or uniform crossover if any improvement is obtained. Further, custom crossover techniques can also be devised based on the problem. Hopefully, this helps.</p><p>Image Sources:</p><ol><li>Single, Two-Point and Uniform Crossover <a href="https://providing.blogspot.com/2015/06/genetic-algorithms-crossover.html?m=1">https://providing.blogspot.com/2015/06/genetic-algorithms-crossover.html?m=1</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c0fdcb405c0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/crossover-operator-the-heart-of-genetic-algorithm-6c0fdcb405c0">Crossover Operator — The Heart of Genetic Algorithm</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>