遗传算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 采用遗传算法解决10城市TSP问题\n",
    "10城市坐标为：\n",
    "- 1： (41, 94)；\n",
    "- 2： (37, 84)；\n",
    "- 3： (54, 67)；\n",
    "- 4： (25, 62)；\n",
    "- 5： (7, 64)；\n",
    "- 6： (2, 99)；\n",
    "- 7： (68, 58)；\n",
    "- 8： (71, 44)；\n",
    "- 9： (54, 62)；\n",
    "- 10： (83, 69)\n",
    "\n",
    "## 思考：\n",
    "\n",
    "- 遗传算法求解问题的性能与哪些因素有关？\n",
    "- 遗传算法的缺陷有哪些？\n",
    "- 有何改进措施？\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import  random\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. 获取临接矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CacDistance(a,b):\n",
    "    \"\"\"\n",
    "    计算两点之间的距离\n",
    "    \"\"\"\n",
    "    a = np.array(a)\n",
    "    b = np.array(b)\n",
    "    c = a-b\n",
    "    distance = np.sqrt(np.sum(c*c))\n",
    "    return distance\n",
    "\n",
    "def CityDistance():\n",
    "    \"\"\"\n",
    "    获取临接矩阵\n",
    "    \"\"\"\n",
    "    locs = [(41, 94),(37, 84),(54, 67),(25, 62),(7, 64),(2, 99),(68, 58),(71, 44),(54, 62),(83, 69)]\n",
    "    n = len(locs)\n",
    "\n",
    "    dis_mat = np.zeros([10,10])\n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1,n):\n",
    "            dist = CacDistance(locs[i],locs[j])\n",
    "            dis_mat[i,j] = dist\n",
    "\n",
    "    for i in range(n):\n",
    "        dis_mat[:,i] = dis_mat[i,:]\n",
    "\n",
    "    return dis_mat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. 遗传算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1交叉"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Cross(p1,p2):\n",
    "    a = np.array(p1).copy()\n",
    "    b = np.array(p2).copy()\n",
    "\n",
    "    # 0~9之间随机生成两个整数,作为映射的起始点和结束点\n",
    "    begin = random.randint(0,9)\n",
    "    end = random.randint(0,9)\n",
    "    # 使 begin 小于 end\n",
    "    if begin > end:\n",
    "        temp = begin\n",
    "        begin = end\n",
    "        end = temp\n",
    "\n",
    "    #print begin,end\n",
    "    # 建立映射关系\n",
    "    cross_map = {}\n",
    "    is_exist = False\n",
    "    # 初步映射\n",
    "    for i in range(begin,end+1):\n",
    "        if a[i] not in cross_map.keys():\n",
    "            cross_map[a[i]] = []\n",
    "        if b[i] not in cross_map.keys():\n",
    "            cross_map[b[i]] = []\n",
    "\n",
    "        cross_map[a[i]].append(b[i])\n",
    "        cross_map[b[i]].append(a[i])\n",
    "\n",
    "\n",
    "    # 处理传递映射 如1:[6],6:[3,1]-->1:[6,3,1],6:[3,1]\n",
    "    # 计算子串中元素出现的个数，个数为2，则该元素为传递的中间结点，如如1:[6],6:[3,1],‘6’出现的次数为2\n",
    "    appear_times = {}\n",
    "    for i in range(begin,end+1):\n",
    "        if a[i] not in appear_times.keys():\n",
    "            appear_times[a[i]] = 0\n",
    "        if b[i] not in appear_times.keys():\n",
    "            appear_times[b[i]] = 0\n",
    "\n",
    "        appear_times[a[i]] += 1\n",
    "        appear_times[b[i]] += 1\n",
    "\n",
    "        if a[i] == b[i]:\n",
    "            appear_times[a[i]] -= 1\n",
    "\n",
    "\n",
    "    for k,v in appear_times.items():\n",
    "        if v == 2:\n",
    "            values = cross_map[k]\n",
    "            for key in values:\n",
    "                cross_map[key].extend(values)\n",
    "                cross_map[key].append(k)\n",
    "                cross_map[key].remove(key)\n",
    "                cross_map[key] = list(set(cross_map[key]))\n",
    "\n",
    "\n",
    "    # 使用映射关系交叉\n",
    "    # 先映射选中的子串\n",
    "    temp = a[begin:end+1].copy()\n",
    "    a[begin:end+1] = b[begin:end+1]\n",
    "    b[begin:end+1] = temp\n",
    "\n",
    "    # 根据映射规则映射剩下的子串\n",
    "    seg_a = a[begin:end+1]\n",
    "    seg_b = b[begin:end+1]\n",
    "\n",
    "    remain = list(range(begin))\n",
    "    remain.extend(range(end+1,len(a)))\n",
    "\n",
    "    for i in remain:\n",
    "        keys = cross_map.keys()\n",
    "        if a[i] in keys:\n",
    "            for fi in cross_map[a[i]]:\n",
    "                if fi not in seg_a:\n",
    "                    a[i] = fi\n",
    "                    break\n",
    "\n",
    "        if b[i] in keys:\n",
    "            for fi in cross_map[b[i]]:\n",
    "                if fi not in seg_b:\n",
    "                    b[i] = fi\n",
    "                    break\n",
    "\n",
    "    return a,b            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 变异"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Variation(s):\n",
    "    c = range(10)\n",
    "    index1,index2 = random.sample(c,2)\n",
    "    temp = s[index1]\n",
    "    s[index1] = s[index2]\n",
    "    s[index2] = temp\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3 计算适应度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cost(s):\n",
    "    dis = CityDistance()\n",
    "    n = len(s)\n",
    "    cost = 0\n",
    "    for i in range(n):\n",
    "        cost += dis[s[i],s[(i+1)%n]]\n",
    "    return -cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 构建遗传算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 获取列表的第三个元素\n",
    "def TakeThird(elem):\n",
    "    \"\"\"\n",
    "    按适应度从大到小，排序时作为sort的key参数\n",
    "    \"\"\"\n",
    "    return elem[2]\n",
    "\n",
    "def CacAdap(population):\n",
    "    \"\"\"\n",
    "    # adap n*4,n为行数，每行包括：个体下标,适应度,选择概率,累积概率\n",
    "    \"\"\"\n",
    "    # 计算每一个个体的适应度,选择概率\n",
    "    adap = []\n",
    "    psum = 0\n",
    "    # 计算适应度\n",
    "    i = 0\n",
    "    for p in population:\n",
    "        icost = np.exp(cost(p))\n",
    "        psum += icost\n",
    "        # 添加个体下标\n",
    "        adap.append([i])\n",
    "        # 添加适应度\n",
    "        adap[i].append(icost)\n",
    "        i += 1\n",
    "    # 计算选择概率\n",
    "    for p in adap:\n",
    "        # 添加选择概率和累积概率，这里累积概率暂时等于选择概率，后面会重新计算赋值\n",
    "        p.append(p[1]/psum)\n",
    "        p.append(p[2])\n",
    "\n",
    "    # 根据适应度从大到小排序\n",
    "    adap.sort(key=TakeThird,reverse=True)\n",
    "    #print adap\n",
    "    # 计算累计概率\n",
    "    n = len(adap)\n",
    "    for i in range(1,n):\n",
    "        p = adap[i][3] + adap[i-1][3]\n",
    "        adap[i][3] = p\n",
    "    \n",
    "    return adap\n",
    "\n",
    "def Chose(adap):\n",
    "    \"\"\"\n",
    "    轮盘选择操作\n",
    "    \"\"\"\n",
    "    chose = []\n",
    "    # 选择次数\n",
    "    epochs = 20 #max(len(adap)/2,20)\n",
    "    #while(len(set(chose)) <2):\n",
    "    #print 'chosing...length %d'%len(set(chose))\n",
    "    n = len(adap)\n",
    "    for a in range(epochs):\n",
    "        p = random.random()\n",
    "        if adap[0][3] >= p:\n",
    "            chose.append(adap[0][0])\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if adap[i][3] >= p and adap[i-1][3] < p:\n",
    "                    chose.append(adap[i][0])\n",
    "                    break\n",
    "\n",
    "    chose = list((chose))\n",
    "    return chose\n",
    "\n",
    "def Cross_Variation(chose,population):\n",
    "    \"\"\"\n",
    "    交叉变异操作\n",
    "    \"\"\"\n",
    "    # 交叉率\n",
    "    p_c = 0.7\n",
    "    # 变异率\n",
    "    p_m = 0.3\n",
    "    # 交叉变异操作\n",
    "    chose_num = len(chose)\n",
    "    sample_times = chose_num//2\n",
    "    for i in range(sample_times):\n",
    "        index1,index2 = random.sample(chose,2)\n",
    "        #print index1,index2\n",
    "        # 参与交叉的父结点\n",
    "        parent1 = population[index1]\n",
    "        parent2 = population[index2]\n",
    "        # 这两个父结点已经交叉，后面就不要参与了，就像这两个人以及结婚，按规矩不能在与其他人结婚了，故从采样样本中移除\n",
    "        chose.remove(index1)\n",
    "        chose.remove(index2)\n",
    "        \n",
    "        p = random.random()\n",
    "        if p_c >= p:\n",
    "            child1,child2 = Cross(parent1,parent2)\n",
    "            #print child1,child2\n",
    "            p1 = random.random()\n",
    "            p2 = random.random()\n",
    "            if p_m > p1:\n",
    "                child1 = Variation(child1)\n",
    "            if p_m > p2:\n",
    "                child2 = Variation(child2)\n",
    "            population.append(list(child1))\n",
    "            population.append(list(child2))\n",
    "    return population"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GA(population):\n",
    "    \"\"\"\n",
    "    一次遗传过程\n",
    "    \"\"\"\n",
    "    \n",
    "    adap = CacAdap(population)\n",
    "\n",
    "    # 选择操作\n",
    "    chose = Chose(adap)\n",
    "    # 交叉变异\n",
    "    population = Cross_Variation(chose,population)\n",
    "        \n",
    "\n",
    "    return population"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5 循环调用遗传算法，直到达到终止条件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_min(population):\n",
    "    loss = []\n",
    "    # 遗传次数\n",
    "    epochs = 51\n",
    "    i = 0\n",
    "    while i < epochs:\n",
    "        adap = []\n",
    "        # 计算适应度\n",
    "        for p in population:\n",
    "            icost = cost(p)\n",
    "            adap.append(icost)\n",
    "        \n",
    "        # 使用遗传算法更新种群\n",
    "        population = GA(population)\n",
    "        \n",
    "        min_cost = max(adap)\n",
    "        if i%10 == 0:\n",
    "            print('epoch %d: loss=%.2f'%(i,-min_cost))\n",
    "        loss.append([i,-min_cost])\n",
    "        i += 1\n",
    "        if i == epochs:\n",
    "            # 输出最优解\n",
    "            p_len = len(population)\n",
    "            for index in range(p_len):\n",
    "                if adap[index] == min_cost:\n",
    "                    print('最优路径:')\n",
    "                    print(population[index])\n",
    "                    print('代价大小:')\n",
    "                    print(-min_cost)\n",
    "                    break\n",
    "    # 打印损失函数变换\n",
    "    loss = np.array(loss)\n",
    "    plt.plot(loss[:,0],loss[:,1])\n",
    "    plt.title('GA')\n",
    "    plt.show()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "epoch 0: loss=313.19\n",
      "epoch 10: loss=243.34\n",
      "epoch 20: loss=242.28\n",
      "epoch 30: loss=242.28\n",
      "epoch 40: loss=242.28\n",
      "epoch 50: loss=242.28\n",
      "最优路径:\n",
      "[0, 5, 4, 3, 8, 6, 7, 9, 2, 1]\n",
      "代价大小:\n",
      "242.27504980994757\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEICAYAAABRSj9aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAG89JREFUeJzt3Xt0XeV95vHvo5tlSViyJQG2LCwudgLpEJwohsSTwDhJwTSNk5mmMaslkEnjXEgKWTSzIDNrpsyqV6dpA4WZhNQN5DakhARoaAaSOo0pEIod2ZiLEQQDNhYyWLbx3ZZvv/njbNkntqxzZJ/jc7TP81lLS+e8+93ybydaj17e8+53KyIwM7P0qip1AWZmVlwOejOzlHPQm5mlnIPezCzlHPRmZinnoDczSzkHvZlZyjnozQBJ8yUtlbRT0obk9eclKavPn0sKSbNKWavZaDnoreJJuh64Ffhr4HTgNOCzwGygLukj4EpgM3BVaSo1Oz7ynbFWySQ1A/3AJyLi3hH6vQ/4OfBpMn8UJkfE3pNTpdmJ8YjeKt27gXHAT3L0uwr4J+CHyfsPFbMos0Jy0FulawM2RsT+oQZJj0vaImm3pPdJagA+BvwgIvYBP8bTNzaGOOit0m0C2iTVDDVExHsioiU5VgV8FNgPPJh0uQuYK6n9ZBdrdjwc9Fbp/g0YBOaN0OcqoAl4VdLrwI+AWuCK4pdnduJqcncxS6+I2CLpJuAbycqanwG7gPOBRqADeD8wF3g669TryPwBuO3kVmw2el51YwZI+iPgWuB3gJ3Ay8AdZJZbzouIdx7RfwqwFpgZEc+e5HLNRsVBb2aWcp6jNzNLOQe9mVnKOejNzFLOQW9mlnJlsbyyra0turq6Sl2GmdmYsnz58o0RkfPGvbII+q6uLnp6ekpdhpnZmCJpbT79PHVjZpZyDnozs5Rz0JuZpZyD3sws5Rz0ZmYp56A3M0s5B72ZWcqN6aB/4fXtfPVnz7N1175Sl2JmVrbGdNCv3bSTbzz8Eq9u3lXqUszMytaYDvrJzeMB6N+6u8SVmJmVr7Ed9C31AKzf4qA3MzuWMR30rY111NVUsX7rnlKXYmZWtsZ00EticnM9/Q56M7NjGtNBDzC5ud5TN2ZmI8gZ9JLqJS2T9JSkVZJuStq/IGm1pJDUltVfkm5Ljj0t6R3FvIApzeM9dWNmNoJ89qMfBOZExA5JtcBjkh4CfgX8FHj4iP5zgenJ14XA7cn3oji9uZ43tu3hwMGgukrF+mfMzMasnCP6yNiRvK1NviIinoyINcOcMg/4XnLeE0CLpMkFq/gIk1vGs/9gsHHHYLH+CTOzMS2vOXpJ1ZJWAhuAxRGxdITuHcC6rPd9SduRP3OBpB5JPQMDA6Op+bdMac4ssez3PL2Z2bDyCvqIOBARFwBTgVmSfmeE7sPNn8QwP3NRRHRHRHd7e85HHh7T0E1Tnqc3MxveqFbdRMQWMnPyl43QrQ/ozHo/FegfdWV5mtLiEb2Z2UjyWXXTLqkleT0e+ADw/AinPAB8Ill9cxGwNSLWF6TaYTSPr2V8bbVH9GZmx5DPiH4ysETS08CvyczR/1TSn0rqIzNif1rSt5L+DwIvA6uBvwc+X4S6D5HE5JZ6XnfQm5kNK+fyyoh4Gpg5TPttwG3DtAdwTUGqy1Pm7lhP3ZiZDWfM3xkLmQ9k12/xiN7MbDipCPopzfVs2L6H/QcOlroUM7Oyk4qgn9wynoMBb2z3TVNmZkdKR9A3e196M7NjSUXQT2nxTVNmZseSiqA/fWhE75U3ZmZHSUXQT6ivpWlcDf1eeWNmdpRUBD0kDyDxiN7M7CjpCfoWP4DEzGw4qQn6Kc31nroxMxtGaoJ+cvN4Nu4YZHD/gVKXYmZWVtIT9Ml2xRu2+aYpM7Ns6Ql6P2nKzGxYKQp63zRlZjac1AT9oSdNeYmlmdlvSU3QN9TV0Dy+1tsVm5kdITVBD75pysxsOKkK+ikt472W3szsCKkK+tOb63l9m4PezCxbzqCXVC9pmaSnJK2SdFPSfqakpZJelPRDSXVJ+7jk/erkeFdxL+GwKc31bN65lz37fNOUmdmQfEb0g8CciHg7cAFwmaSLgL8CbomI6cCbwKeS/p8C3oyIc4Bbkn4nhZdYmpkdLWfQR8aO5G1t8hXAHODHSft3gY8kr+cl70mOv1+SClbxCIbujvWTpszMDstrjl5StaSVwAZgMfASsCUi9idd+oCO5HUHsA4gOb4VaB3mZy6Q1COpZ2Bg4MSuIjElGdH3e0RvZnZIXkEfEQci4gJgKjALOHe4bsn34UbvcVRDxKKI6I6I7vb29nzrHdHpfnasmdlRRrXqJiK2AA8DFwEtkmqSQ1OB/uR1H9AJkBxvBjYXothc6murmdRY5xG9mVmWfFbdtEtqSV6PBz4A9AJLgD9Iul0F/CR5/UDynuT4LyPiqBF9sUxurud13zRlZnZITe4uTAa+K6mazB+GeyLip5KeA+6W9BfAk8AdSf87gO9LWk1mJD+/CHUfu9jm8fS9uetk/pNmZmUtZ9BHxNPAzGHaXyYzX39k+x7gYwWp7jhMaaln2SubSvXPm5mVnVTdGQuZEf22PfvZObg/d2czswqQuqAf2q7Ym5uZmWWkLuiH7o715mZmZhkpDHqP6M3MsqUu6E+bUI/k/W7MzIakLujraqpoaxrnJ02ZmSVSF/SQ2a7Yz441M8tIZdBPbh7vqRszs0Q6g76lnvVbdnMSd14wMytb6Qz65np27j3Atj2+acrMLKVBP/SkKc/Tm5mlMug7JmaC/rU3HfRmZqkM+q7WRgDWbvIulmZmqQz6iQ21nDKuhrWbdpa6FDOzkktl0EtiWlsDazyiNzNLZ9ADTGtt9IjezIwUB31XawN9b+5m34GDpS7FzKykUhv001ob2X8w6N/ilTdmVtlSG/RDK288T29mlS5n0EvqlLREUq+kVZKuTdrfLunfJD0j6Z8kTcg650ZJqyW9IOnSYl7AsXS1NgB4nt7MKl4+I/r9wPURcS5wEXCNpPOAbwE3RMS/A+4HvgyQHJsPvA24DPiGpOpiFD+S9lPGMb62mjUbPaI3s8qWM+gjYn1ErEhebwd6gQ7gLcAjSbfFwH9KXs8D7o6IwYh4BVgNzCp04blIYlprg0f0ZlbxRjVHL6kLmAksBZ4FPpwc+hjQmbzuANZlndaXtB35sxZI6pHUMzAwMLqq89TV2sgaB72ZVbi8g15SE3AvcF1EbAP+M5lpnOXAKcDeoa7DnH7UfsERsSgiuiOiu729ffSV52FaWwPrNu/mwEFvV2xmlasmn06SasmE/F0RcR9ARDwP/G5yfAbwe0n3Pg6P7gGmAv2FKng0ulob2XvgIOu37mbqxIZSlGBmVnL5rLoRcAfQGxE3Z7WfmnyvAv4b8M3k0APAfEnjJJ0JTAeWFbrwfEw7tPLGH8iaWeXKZ+pmNnAlMEfSyuTrcuAKSb8BniczYv82QESsAu4BngN+BlwTEQeKUn0Oh9fSe57ezCpXzqmbiHiM4efdAW49xjkLgYUnUFdBnD6hnrqaKo/ozayipfbOWICqKjFtUgNrNnpEb2aVK9VBD0O7WHpEb2aVK/VB39XawNrNOznoJZZmVqFSH/TT2hrZs+8gG7YPlroUM7OSSH3QD21u5pU3ZlapKiDohx4U7qA3s8qU+qCf3FxPbbW8L72ZVazUB31NdRWdE72LpZlVrtQHPWS2QvC+9GZWqSok6BtZu2knEV5iaWaVpyKCvqu1gZ17D7Bxx97cnc3MUqYign5am1femFnlqoigP7yLpefpzazyVETQd7SMp7pKvOoRvZlVoIoI+rqaKjpaxntEb2YVqSKCHjJLLD1Hb2aVqGKCvqu10SN6M6tIFRP001ob2Lp7H1t2eYmlmVWWigl6r7wxs0qVM+gldUpaIqlX0ipJ1ybtF0h6InlYeI+kWUm7JN0mabWkpyW9o9gXkY+utsx2xZ6nN7NKk/Ph4MB+4PqIWCHpFGC5pMXAV4GbIuIhSZcn7y8B5gLTk68LgduT7yU1dWIDEt7zxswqTs4RfUSsj4gVyevtQC/QAQQwIenWDPQnr+cB34uMJ4AWSZMLXvko1ddWM3lCvUf0ZlZx8hnRHyKpC5gJLAWuA34u6W/I/MF4T9KtA1iXdVpf0rb+iJ+1AFgAcMYZZ4y+8uMwrbXRT5oys4qT94exkpqAe4HrImIb8DngSxHRCXwJuGOo6zCnH7VtZEQsiojuiOhub28ffeXHoautgbX+MNbMKkxeQS+plkzI3xUR9yXNVwFDr38EzEpe9wGdWadP5fC0TklNa21k0869bNuzr9SlmJmdNDmnbiSJzGi9NyJuzjrUD1wMPAzMAV5M2h8AviDpbjIfwm6NiN+atimVoQeFP756E+ec2pTXOVJmaWZ11XD/oWJmVv7ymaOfDVwJPCNpZdL2FeDTwK2SaoA9JPPtwIPA5cBqYBfwyYJWfAKGwv2z/3f5qM77zMVncePcc4tRkplZ0akcnrrU3d0dPT09J+XfeuQ3A2zZnf/UzX0r+vj1K5t5/Ib309xQW8TKzMxGR9LyiOjO1W9Uq27S4H0zRvfB7/RTm5h766N8/4k1fGHO9CJVZWZWPBWzBcLxOnfyBC55Szvf/tUa9uw7UOpyzMxGzUGfh89dfDabdu7lRz3rcnc2MyszDvo8zDpzEjPPaGHRoy+z/8DBUpdjZjYqDvo8SOKzF5/Nus27+X/PlMVKUTOzvDno8/TBc0/j7PZGvvmvL1MOK5XMzPLloM9TVZX4zMVn07t+G4+8uLHU5ZiZ5c1BPwofuaCD0yfUc/vDq0tdiplZ3hz0o1BXU8WfvPdMnnh5MyvXbSl1OWZmeXHQj9L8WWcwob6Gbz78UqlLMTPLi4N+lJrG1fCJd3fx8+de56WBHaUux8wsJwf9cbh6dhd11VV8/Zeeqzez8uegPw5tTeO4+j1d3L/yNZ7r31bqcszMRuSgP06fv+QcJtTX8pcP9Za6FDOzETnoj1NzQy1fnHMOj764kUd+M1DqcszMjslBfwKufPc0pk4cz18+9DwHD/puWTMrTw76EzCuppovX/oWetdv4/4nXyt1OWZmw3LQn6DfP38K509t5mv//IL3qzezspQz6CV1SloiqVfSKknXJu0/lLQy+VqT9TxZJN0oabWkFyRdWswLKLWqKnHD3LfSv3UP33l8TanLMTM7Sj6PEtwPXB8RKySdAiyXtDgiPj7UQdLXgK3J6/OA+cDbgCnALyTNiIjUDnffc3Ybc956Kl9fspqPd3cysbGu1CWZmR2Sc0QfEesjYkXyejvQC3QMHZck4A+Bf0ia5gF3R8RgRLwCrAZmFbrwcnPD3Leyc3A//9s3UZlZmRnVHL2kLmAmsDSr+b3AGxHxYvK+A8h+5l4fWX8Y0mrGaafwh92dfP+JNby6aVepyzEzOySfqRsAJDUB9wLXRUT27aBXcHg0D6BhTj9q7aGkBcACgDPOOCPfMsralz44g5+s7Od9f70EDfe/wjFcMqOdb38y9f/RY2YlklfQS6olE/J3RcR9We01wH8E3pnVvQ/ozHo/Feg/8mdGxCJgEUB3d3cqFqGfNqGe73zyXfxqdf4PJnnkxY2seNVbHptZ8eQM+mQO/g6gNyJuPuLwB4DnI6Ivq+0B4AeSbibzYex0YFmB6i17F57VyoVntebdv6pKrFy3hX0HDlJb7dWuZlZ4+STLbOBKYE7WcsrLk2Pz+e1pGyJiFXAP8BzwM+CaNK+4OVGtTeMAeHPn3hJXYmZplXNEHxGPMfy8OxFx9THaFwILT6iyCtGaLMXctHMvp06oL3E1ZpZGnisosUlJ0G/2iN7MisRBX2LZI3ozs2Jw0JfY0Bz9ph2DJa7EzNLKQV9iLeNrqZKnbsyseBz0JVZVJSY21HnqxsyKxkFfBlqb6jx1Y2ZF46AvA5Ma6zx1Y2ZF46AvA62N4zx1Y2ZF46AvA5mpGwe9mRWHg74MTGqsY+vufew7cLDUpZhZCjnoy8DQTVNv7vKo3swKz0FfBiY1Zm6a8geyZlYMDvoy0NqUbIPgeXozKwIHfRnwfjdmVkwO+jJwaAdL3zRlZkXgoC8DLQ11VMkjejMrDgd9Gaj2fjdmVkQO+jIxqbGOzf4w1syKwEFfJlqb6ti003P0ZlZ4OYNeUqekJZJ6Ja2SdG3WsS9KeiFp/2pW+42SVifHLi1W8Wni/W7MrFhyPhwc2A9cHxErJJ0CLJe0GDgNmAecHxGDkk4FkHQeMB94GzAF+IWkGRFxoDiXkA7ewdLMiiXniD4i1kfEiuT1dqAX6AA+B/yviBhMjm1ITpkH3B0RgxHxCrAamFWM4tNkUmMdW3btY7/3uzGzAhvVHL2kLmAmsBSYAbxX0lJJ/yrpXUm3DmBd1ml9SZuNoC25O3az97sxswLLO+glNQH3AtdFxDYy0z4TgYuALwP3SBKgYU6PYX7eAkk9knoGBgaOq/g08X43ZlYseQW9pFoyIX9XRNyXNPcB90XGMuAg0Ja0d2adPhXoP/JnRsSiiOiOiO729vYTuYZUOHx3rIPezAorn1U3Au4AeiPi5qxD/wjMSfrMAOqAjcADwHxJ4ySdCUwHlhW68LQZmrrZ6BG9mRVYPqtuZgNXAs9IWpm0fQW4E7hT0rPAXuCqiAhglaR7gOfIrNi5xitucvN+N2ZWLDmDPiIeY/h5d4A/PsY5C4GFJ1BXxWlpqEPyHL2ZFZ7vjC0T1VViUkOdp27MrOAc9GXE+92YWTE46MuI7441s2Jw0JcRb2xmZsXgoC8j3tjMzIrBQV9GvN+NmRWDg76MtCY3Tb25a1+JKzGzNHHQl5HWZL8bz9ObWSE56MuI97sxs2Jw0JeRoakbfyBrZoXkoC8jrcmIfpP3uzGzAnLQlxHvd2NmxeCgLyPVVWJiQ52nbsysoBz0ZcbbIJhZoTnoy0xrYx2bvOrGzArIQV9mvN+NmRWag77MeOrGzArNQV9mWhvH8ab3uzGzAnLQlxnvd2NmhZYz6CV1SloiqVfSKknXJu1/Luk1SSuTr8uzzrlR0mpJL0i6tJgXkDaHtkHw9I2ZFUjOh4MD+4HrI2KFpFOA5ZIWJ8duiYi/ye4s6TxgPvA2YArwC0kzIuJAIQtPq0Mbm+0YBE4pbTFmlgo5R/QRsT4iViSvtwO9QMcIp8wD7o6IwYh4BVgNzCpEsZXA+92YWaGNao5eUhcwE1iaNH1B0tOS7pQ0MWnrANZlndbHMH8YJC2Q1COpZ2BgYNSFp5Wnbsys0PIOeklNwL3AdRGxDbgdOBu4AFgPfG2o6zCnx1ENEYsiojsiutvb20ddeFpNTPa78YjezAolr6CXVEsm5O+KiPsAIuKNiDgQEQeBv+fw9Ewf0Jl1+lSgv3Alp9uh/W68g6WZFUg+q24E3AH0RsTNWe2Ts7p9FHg2ef0AMF/SOElnAtOBZYUrOf1805SZFVI+q25mA1cCz0hambR9BbhC0gVkpmXWAJ8BiIhVku4BniOzYucar7gZnUmN3sHSzAonZ9BHxGMMP+/+4AjnLAQWnkBdFa2tqY4XXt9e6jLMLCV8Z2wZ8tSNmRWSg74MTWocx5bd3u/GzArDQV+G2prqiPB+N2ZWGA76MuSbpsyskBz0ZWgo6P0AEjMrBAd9GRra2MwjejMrBAd9GTq0sZmfHWtmBeCgL0Pe78bMCslBX4aqq0TL+Fo2e47ezArAQV+mWpvGeerGzArCQV+mvN+NmRWKg75MtXobBDMrkHx2r7QSaG2qY/FzO5l766OlLuWk6mpt4LMXn83bO1tKXYpZajjoy9RHZ3YwsH2Qg0c9myu9IuDxlzbx0LOvc/GMdv70/dN557SJuU80sxEpovRJ0t3dHT09PaUuw8rA9j37+P4Ta/nWo6+weedeZp/TyhfnTOeis1pLXZpZ2ZG0PCK6c/Zz0Fs52rV3P3c98Sp/98jLbNwxyBmTGhhX44+ULH0+/q5O/uS9Zx3XufkGvadurCw11NXw6fedxZXvnsbdy15l2ZrNpS7JrCjamsYV/d9w0FtZq6+t5urZZ3L17DNLXYrZmOX/FjYzS7mcQS+pU9ISSb2SVkm69ojjfyYpJLUl7yXpNkmrJT0t6R3FKt7MzHLLZ+pmP3B9RKyQdAqwXNLiiHhOUifwQeDVrP5zgenJ14XA7cl3MzMrgZwj+ohYHxErktfbgV6gIzl8C/BfgOylO/OA70XGE0CLpMmFLdvMzPI1qjl6SV3ATGCppA8Dr0XEU0d06wDWZb3v4/AfhuyftUBSj6SegYGBURVtZmb5yzvoJTUB9wLXkZnO+a/Afx+u6zBtRy3Wj4hFEdEdEd3t7e35lmFmZqOUV9BLqiUT8ndFxH3A2cCZwFOS1gBTgRWSTiczgu/MOn0q0F/Ios3MLH/5rLoRcAfQGxE3A0TEMxFxakR0RUQXmXB/R0S8DjwAfCJZfXMRsDUi1hfvEszMbCQ5t0CQ9O+BR4FngINJ81ci4sGsPmuA7ojYmPxh+D/AZcAu4JMRMeL+BpIGgLXHeQ1twMbjPHes8jVXBl9zZTiRa54WETnnvstir5sTIaknn70e0sTXXBl8zZXhZFyz74w1M0s5B72ZWcqlIegXlbqAEvA1VwZfc2Uo+jWP+Tl6MzMbWRpG9GZmNgIHvZlZyo3poJd0maQXki2Rbyh1PcUg6U5JGyQ9m9U2SdJiSS8m31P1BO1jbY2d5uuWVC9pmaSnkmu+KWk/U9LS5Jp/KKmu1LUWkqRqSU9K+mnyPu3Xu0bSM5JWSupJ2or+ez1mg15SNfB1MtsinwdcIem80lZVFN8hc/NZthuAf4mI6cC/JO/TZGhr7HOBi4Brkv9v03zdg8CciHg7cAFwWXJn+V8BtyTX/CbwqRLWWAzXktkRd0jarxfgP0TEBVlr54v+ez1mgx6YBayOiJcjYi9wN5ktklMlIh4Bjnxg6jzgu8nr7wIfOalFFdkIW2On9rqTbb13JG9rk68A5gA/TtpTdc2SpgK/B3wreS9SfL0jKPrv9VgO+ry2Q06p04b2D0q+n1rieoome2tsUn7dyTTGSmADsBh4CdgSEfuTLmn7Hf9bMs+zGNpapZV0Xy9k/nj/s6TlkhYkbUX/vR7LDwfPaztkG7uyt8aOiG2ZAV96RcQB4AJJLcD9wLnDdTu5VRWHpA8BGyJiuaRLhpqH6ZqK680yOyL6JZ0KLJb0/Mn4R8fyiL6St0N+Y+ipXcn3DSWup+CG2RobKuC6ASJiC/Awmc8nWiQNDcjS9Ds+G/hwsiHi3WSmbP6W9F4vABHRn3zfQOaP+SxOwu/1WA76XwPTk0/p64D5ZLZIrgQPAFclr68CflLCWgpuuK2xE6m9bkntyUgeSeOBD5D5bGIJ8AdJt9Rcc0TcGBFTk23O5wO/jIg/IqXXCyCpMXnuNpIagd8FnuUk/F6P6TtjJV1OZhRQDdwZEQtLXFLBSfoH4BIyW5m+AfwP4B+Be4AzyDyY/WMRceQHtmPWsbbGJjNPn8rrlnQ+mQ/iqskMwO6JiP8p6SwyI95JwJPAH0fEYOkqLbxk6ubPIuJDab7e5NruT97WAD+IiIWSWiny7/WYDnozM8ttLE/dmJlZHhz0ZmYp56A3M0s5B72ZWco56M3MUs5Bb2aWcg56M7OU+/8p9OG+m5y0gAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 初始化\n",
    "s1 = [1,2,3,4,5,6,7,8,9,0]\n",
    "s2 = [5,4,6,9,2,1,7,8,3,0]\n",
    "s3 = [0,1,2,3,7,8,9,4,5,6]\n",
    "s4 = [1,2,3,4,5,7,6,8,9,0]\n",
    "population = [s1,s2,s3,s4]\n",
    "# 调用\n",
    "find_min(population)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}