{"cells":[{"metadata":{"_uuid":"5350e1753524a898305f16d963a7325410adf16e"},"cell_type":"markdown","source":"### **Original Research Article** \n### [**John R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection”, MIT Press, 1992, pages 162-169.**](https://doc.lagout.org/science/Artificial%20Intelligence/Evolutionary%20computation/Genetic%20programming%20Complex%20adaptive%20systems%20-%20Koza%20J.R..pdf)\n\n---\n![](https://cdn-images-1.medium.com/max/720/1*BYDJpa6M2rzWNSurvspf8Q.png)\n\n## **Outline of Notebook**\n\n* [**Genetic Algorithm**](#Genetic Algorithm)\n* [**Search space**](#Search-space)\n* [**Operators of Genetic Algorithms**](#Operators-of-Genetic-Algorithms)\n* [**Psuedo Code of GA**](#Psuedo-Code-of-GA)\n* [**Example** : **Buy &  Sell Apple Share price Analysis using GeneticOptimization**](#**Example**-:-**Buy-&--Sell-Apple-Share-price-Analysis-using GeneticOptimization**)\n* [**GPlearn Example with Sklearn**](#GPlearn-Example-with-Sklearn)\n\n# **Genetic Algorithm**\n\n---\n* Genetic Algorithms (GA) are adaptive heuristic search algorithms belonging to most evolutionary algorithms. Genetic algorithms are based on the notions of natural selection and genetics. It's an intelligent use of historical data-driven random search to guide the search for the best performing region in the solution's space.**They are commonly used to generate high quality solutions for optimization and search problems.**\n* **Genetic algorithms simulate the process of natural selection**. This means that species that can adapt to changes in their environment will survive, reproduce, and move on to the next generation. In simple words, they simulate the \"survival of the fittest\" among individuals of successive generations to solve a problem. **Each generation consists of a population of individuals** and each individual represents a point in the search space and a possible solution. Each individual is represented as a string / whole / floating / bits. This chain is analogous to the chromosome.\n* **Genetic algorithms** are based on an ***analogy to the genetic structure and behavior of the chromosome of the population.*** The following GA is based on this analogy:\n    1. People in the population are fighting for resources and partners.\n    1. Those who succeed (in better shape) make more offspring than others\n    1. The genes of the \"fittest\" father spread over the entire generation, that is, sometimes they produce the offspring of the parents, which is better than the two parents.\n    1. Thus, each subsequent generation adapts better to their environment.\n\n### **Search space**\n\n---\n\n* The population of the persons is kept in the search space. Each person represents a solution in the search space for a given problem. Each individual is coded as a finite-length vector (analogous to the chromosome) of the components. These variable components are analogous to the genes. Thus, a chromosome (individual) consists of several genes (variable components).\n\n![](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/genetic-algorithm.png)\n\n* A physical fitness score is given to each individual that shows the ability of an individual to \"compete\". The individual who has an optimal physical fitness score (or almost optimal) is sought.\n\n* **GA maintain the population of n individuals (chromosome / solutions) along with their physical fitness scores.** People with better physical fitness scores are more likely to reproduce than others. Individuals with better physical fitness scores are matched and produce better offspring by combining the chromosomes of the parents. The size of the population is static, so the room must be created for newcomers. Therefore, some people die and are replaced by newcomers who eventually create a new generation when all the mating opportunities of the old population are exhausted. It is expected that successive generations arrive better solutions, while those that adapt less to death.\n\n* Each new generation has on average more \"better genes\" than the individual (solution) of previous generations. Thus, each new generation has better \"partial solutions\" than previous generations. Once the offspring produced no significant difference with the offspring produced by previous populations, the population is convergent. It is said that the algorithm converges to a set of solutions for the problem.\n\n### **Operators of Genetic Algorithms**\n\n---\n\nOnce the initial generation is created, the algorithm evolve the generation using following operators –  \n**1) Selection Operator:** The idea is to give preference to the individuals with good fitness scores and allow them to pass there genes to the successive generations.  \n**2) Crossover Operator:** This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –  \n![](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/genetic-algorithm1.png)  \n**3) Mutation Operator:** The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence. For example –  \n![](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/genetic-algorithm2.png)  \n\n### **Psuedo Code of GA**\n\n---\nThe whole algorithm can be summarized as –\n\n<pre>\n1) Randomly initialize populations p\n2) Determine fitness of population\n3) Untill convergence repeat:\n      a) Select parents from population\n      b) Crossover and generate new population\n      c) Perform mutation on new population\n      d) Calculate fitness for new population\n</pre>\n"},{"metadata":{"_uuid":"7871492e72e50d572860c3ea29c9e3e32031e0e7"},"cell_type":"markdown","source":"## **Example** : **Buy &  Sell Apple Share price Analysis using GeneticOptimization**\n\n---"},{"metadata":{"trusted":true,"_uuid":"17ffd46561a90a361ce65f5fbc30f2fce1ac6e15"},"cell_type":"code","source":"import pandas as pd\nimport requests\nimport json\nfrom pandas.io.json import json_normalize\nimport matplotlib.pyplot as plt\n%matplotlib inline\nplt.style.use(\"fivethirtyeight\")\nimport numpy as np\nimport seaborn as sns\n\nfrom deap import base\nfrom deap import creator\nfrom deap import tools\nfrom deap import algorithms\n\nimport random\nimport warnings\nwarnings.simplefilter(\"ignore\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"09be15c8579ed059420f1c5a12c6eea21b90daa2"},"cell_type":"code","source":"# pull last 7 years of IBM stock data\nr = requests.get('https://www.quandl.com/api/v3/datasets/EOD/AAPL.json?api_key=9xqjN15_V3Mm13QKpFDg&start_date=2012-11-01&end_date=2018-12-31')\ncolumn_names = r.json()['dataset']['column_names']\n# get data and turn it into a numpy array\ndata = r.json()['dataset']['data']\ndata = [row[4] for row in data]\ndata = np.array(data)\nprint('APPLE closing price for past 7 years:')\nprint(data)\nprint('{} sessions'.format(data.size))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"d8867d798a6f2a911a4bc1e618fd0592b0fd4d54"},"cell_type":"code","source":"plt.figure(figsize=(20,8))\nplt.plot(data)\nplt.xlabel(\"Total Session\")\nplt.ylabel(\"Price in $(Dollar)\")\nplt.title(\"7 Year Stock Price of APPLE\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"1c6ceec865780ca967470b28859f9a3ff8c2c4d1"},"cell_type":"code","source":"# create genetic models\n\n# -1 will be sell points, 0 will be hold points, 1 will by buy points. algo will evolve to generate the most\n# profitable buy and sell points in a stock. fitness will be evaluated on a first in, first out manner.\n\ncreator.create(\"FitnessMax\", base.Fitness, weights=(1.0,))\ncreator.create(\"Individual\", list, fitness=creator.FitnessMax)\n\ntoolbox = base.Toolbox()\ntoolbox.register(\"attr_int\", random.randint, -1, 1)\ntoolbox.register(\"individual\", tools.initRepeat, creator.Individual,\n                 toolbox.attr_int, n=data.size)\ntoolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"1dbd8db813087e417c207344c96e61884d8711a3"},"cell_type":"code","source":"# generate an example individual\n\nind1 = toolbox.individual()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c2ffefd6573bf122d2191975179f591e01ad7203"},"cell_type":"code","source":"ind11 = pd.DataFrame(ind1, columns=['Counts'])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"399e81b1f366f2a1401dc48384f04559528f4dee"},"cell_type":"code","source":"def count_plot(ind11):\n    plt.figure(figsize=(20,8))\n    ind11['Counts'].value_counts().plot(kind=\"bar\")\n    plt.xlabel(\"Individual\")\n    plt.ylabel(\"Counts\")\n# plt.title(\"7 Year Stock Price of APPLE\")\ncount_plot(ind11)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"aa68c2585ae085309f69207259f3bc9d1c552a85"},"cell_type":"code","source":"# create seperate lists to know where to mark each buy and sell point on the data\nbuy_markers = [i for i, x in enumerate(ind1) if x == 1]\nsell_markers = [i for i, x in enumerate(ind1) if x == -1]\n# buy_markers = pd.DataFrame(buy_markers, columns=['Counts'])\n# sell_markers = pd.DataFrame(sell_markers, columns=['Counts'])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c3bab490bc397ef7fbf60d17f8c0896eeb99ba92"},"cell_type":"code","source":"# what a generation 0 random individual looks like currently\nplt.figure(figsize=(20,8))\nplt.plot(data)\nplt.plot(data, color='r', marker='v', markevery=sell_markers, linewidth=0)\nplt.plot(data, color='g', marker='^', markevery=buy_markers, linewidth=0)\nplt.xlabel(\"Total Session\")\nplt.ylabel(\"Price in $(Dollar)\")\nplt.title(\"7 Year Stock Price of APPLE\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c64518a61e36a875cc6850ede779f9b67b009cfe"},"cell_type":"code","source":"# the evaluation function will only calculate long trades\n# short trades will 'sell' stock if they are available\n# the trade at index 0 will always be sold on a short trade\n\ncommission_cost = 2.99\n\ndef evalFitness(individual):\n    trades = []\n    profit = 0\n    for i in range(data.size):\n        if individual[i] == 1:\n            trades.append(data[i])\n            profit -= commission_cost\n        if individual[i] == -1:\n            if len(trades) > 0:\n                profit += (data[i] - trades[0]) - commission_cost\n    return (profit,)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"174961273a5d8c3f1f7879fe86b42110214b644c"},"cell_type":"code","source":"# testing our randomly generated individual.\n# it's going to be a crappy individual to start off\nprint (evalFitness(ind1))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"04d047384bc687761e36621af347586440ac0afc"},"cell_type":"code","source":"# set up genetic operators for evolution of the population\ntoolbox.register(\"evaluate\", evalFitness)\ntoolbox.register(\"mate\", tools.cxOnePoint)\ntoolbox.register(\"mutate\", tools.mutGaussian, mu=0, sigma=1, indpb=0.05)\ntoolbox.register(\"select\", tools.selTournament, tournsize=3)\n\nstats = tools.Statistics(lambda ind: ind.fitness.values)\nstats.register(\"avg\", np.mean)\nstats.register(\"std\", np.std)\nstats.register(\"min\", np.min)\nstats.register(\"max\", np.max)\n\npop = toolbox.population(n=300)\nhof = tools.HallOfFame(1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"0900c633b9604301a6b8f8227899065a44000201","scrolled":false},"cell_type":"code","source":"# evolve!\npop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=400, stats=stats, halloffame=hof, verbose=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c3c578463aa9158169cb7d976829d75a1908a6ef"},"cell_type":"code","source":"# plot results\navg = log.select('gen', 'avg')\nmax = log.select('gen', 'max')\n\nf, (ax1, ax2) = plt.subplots(1, 2, sharey=True,figsize=(20,8))\nax1.set_title('Average Fitness Over Time')\nax1.plot(avg[0], avg[1])\nax2.set_title('Max Fitness Over Time')\nax2.plot(max[0], max[1])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"8d3eeafea2980576d041a4ebbd3c52f316290f3e"},"cell_type":"code","source":"# plot the best organism and see how it did compared to the randomly generated one\n\nbest_ind = tools.selBest(pop, 1)[0]\n\nbuy_markers = [i for i, x in enumerate(best_ind) if x == 1]\nsell_markers = [i for i, x in enumerate(best_ind) if x == -1]\n\nplt.figure(figsize=(20,8))\nplt.plot(data)\nplt.plot(data, color='r', marker='v', markevery=sell_markers, linewidth=0)\nplt.plot(data, color='g', marker='^', markevery=buy_markers, linewidth=0)\nplt.xlabel(\"Total Session\")\nplt.ylabel(\"Price in $(Dollar)\")\nplt.title(\"7 Year Stock Price of APPLE\")","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"e89f3bd075d60c0afe4c7ccb3723a2b841197f23"},"cell_type":"markdown","source":"# **GPlearn Example with Sklearn**\n---"},{"metadata":{"trusted":true,"_uuid":"fd9f6d0e44f03aeb9c5a1990c6dc17d8d22621e4"},"cell_type":"code","source":"from gplearn.genetic import SymbolicRegressor\nfrom sklearn.utils.random import check_random_state\nimport numpy as np","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"6cb1e5aa509f090b141629cb89056795798dd2da"},"cell_type":"code","source":"random_engine = check_random_state(0)\nX_train = random_engine.uniform(-1, 1, 10000).reshape(-1, 1)\nY_train = np.sinh(X_train)\nX_test = random_engine.uniform(-1, 1, 10000).reshape(-1, 1)\nY_test = np.sinh(X_test)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"0d1016aa06f45ef2c1433b033015697469cc0db4"},"cell_type":"code","source":"est_gp = SymbolicRegressor(population_size=5000, generations=50,\n                               stopping_criteria=0.01, p_crossover=0.6,\n                               p_subtree_mutation=0.1,\n                               p_hoist_mutation=0.1, p_point_mutation=0.1,\n                               max_samples=0.9, verbose=1,\n                               parsimony_coefficient=0.01, n_jobs=1,\n                               function_set=('add', 'mul', 'max'))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"af09bb961586da61fa4dca1a6c4181bdaabb8687"},"cell_type":"code","source":"est_gp.fit(X_train, Y_train)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"b4d36234566da364ea671c66d64e8caab5219678"},"cell_type":"code","source":"score_train = est_gp.score(X_train, Y_train)\nscore_test = est_gp.score(X_test, Y_test)\npredicted = est_gp.predict(X_test)\nprint(score_train, score_test)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"61e8d20411c85f4e980de789e549b5919a764cef"},"cell_type":"code","source":"plt.figure(figsize=(20,8))\nplt.plot(Y_test[:100])\nplt.plot(predicted[:100])\nplt.xlabel(\"100 Result\")\nplt.ylabel(\"Values\")\nplt.legend()\nplt.title(\"Prediction vs Actual Result Analysis\")","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"d8c24f4e3a8bab162ece147e507df9b2bf52f812"},"cell_type":"markdown","source":"## **References :**\n1. https://codereview.stackexchange.com/questions/194947/genetic-algorithm-for-traveling-salesman\n2. https://www.researchgate.net/post/Using_genetic_algorithm_for_time_series_prediction_and_preprocessing_the_data\n3. LinkedIn: https://www.linkedin.com/pulse/introduction-optimization-genetic-algorithm-ahmed-gad/\n4. KDnuggets: https://www.kdnuggets.com/2018/03/introduction-optimization-with-genetic-algorithm.html\n5. TowardsDataScience: https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b\n6. SlideShare: https://www.slideshare.net/AhmedGadFCIT/introduction-to-optimization-with-genetic-algorithm-ga"}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}