МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ПОЛТАВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

ІМЕНІ ЮРІЯ КОНДРАТЮКА
Навчально-науковий інститут інформаційних технологій і механотроніки

Кафедра комп’ютерних та інформаційних технологій і систем


Курсова робота
з навчальної дисципліни

«Генетичні алгоритми»
на тему:

«Оптимізація транспортних перевезень»

Виконав: студент 501 – ТН Бєлан Федір Олегович Перевірила: Скакаліна Олена Вікторівна

Полтава

2020

Зміст

РОЗДІЛ 1. ОГЛЯД ОСНОВНИХ ВИДІВ ГЕНЕТИЧНИХ АЛГОРИТМІВ

• 
  знаходження глобального, або надоптимального вирішення;
  
• 
  вичерпання числа поколінь, що відпущені на еволюцію;
  
• 
  вичерпання часу, відпущеного на еволюцію.
  

• 
  У комбінаторній хімії — метод дизайну бібліотеки шляхом оцінки відповідності певних бажаних властивостей (пр., рівня активності в біологічних пошуках, або розрахунково визначених властивостей набору речовин), передбачених за допомогою функції, встановленої статистичними методами при аналізі співвідношення структура — властивість. Ще більш оптимальний дизайн пов'язаний з евристичним процесом, який нагадує генетичну селекцію, де застосовується реплікація, мутація, вилучення.
  

• 
  У хемометриці — механізм оптимізації, заснований на механізмі дарвінівської еволюції, де використовуються випадкові мутації, процедури схрещення та відбору для розробки кращої моделі чи розв'язку порівняно з тим, які було отримано, виходячи зі стартової сукупності чи вибірки.
  

• 
  У комп'ютерній хімії — комп'ютерний метод генерування та тестування комбінацій можливих вхідних параметрів для знаходження оптимальних вихідних значень. Використовується для оптимізації у випадку систем з великою кількістю змінних параметрів, зокрема при конформаційному аналізі багатоатомних складних молекул. Включає методи, що базуються на поняттях природної еволюції, такі як генетична комбінація, мутація та природний відбір.
  

РОЗДІЛ 2. АНАЛІЗ ПРЕДМЕТНЫХ ОБЛАСТЕЙ ДЛЯ ФОРМУЛЮВАННЯ ЗАДАЧІ ГЕНЕТИЧНИХ АЛГОРИТМІВ

1. 
   Оптимізація функцій
   
2. 
   Оптимізація запитів в базах даних
   
3. 
   Різноманітні задачі на графах (задача комівояжера, розфарбування)
   
4. 
   Налаштування і навчання штучної нейронної мережі
   
5. 
   Задачі компоновки
   
6. 
   Створення розкладів
   
7. 
   Ігрові стратегії
   
8. 
   Апроксимація функцій
   
9. 
   Штучне життя
   
10. 
    Біоінформатика (згортання білків)
    
11. 
    Синтез конструкцій антен
    

РОЗДІЛ 3. ОПТИМІЗАЦІЇ ТРАНСПОРТНИХ ПЕРЕВЕЗЕНЬ МЕТОДОМ ГЕНЕТИЧНИХ АЛГОРИТМІВ.

3.1 Вибір методу для виконання поставленої задачі

3.2 Програмна реалізація

3.2.1. Лістинг файлу алгоритму «Algoritm.js»

    doCrossover(queue[i], queue[i+1]);

  }

}
function doCrossover(x, y) {

  child1 = getChild('next', x, y);

  child2 = getChild('previous', x, y);

  population[x] = child1;

  population[y] = child2;

}

function getChild(fun, x, y) {

  solution = new Array();

  var px = population[x].clone();

  var py = population[y].clone();

  var dx,dy;

  var c = px[randomNumber(px.length)];

  solution.push(c);

  while(px.length > 1) {

    dx = px[fun](px.indexOf(c));

    dy = py[fun](py.indexOf(c));

    px.deleteByValue(c);

    py.deleteByValue(c);

    c = dis[c][dx] < dis[c][dy] ? dx : dy;

    solution.push(c);

  }

  return solution;

}

function mutation() {

  for(var i=0; i

    if(Math.random() < MUTATION_PROBABILITY) {

      if(Math.random() > 0.5) {

        population[i] = pushMutate(population[i]);

      } else {

        population[i] = doMutate(population[i]);

      }

      i--;

    }

  }

}

function preciseMutate(orseq) {  

  var seq = orseq.clone();

  if(Math.random() > 0.5){

    seq.reverse();

  }

  var bestv = evaluate(seq);

  for(var i=0; i<(seq.length>>1); i++) {

    for(var j=i+2; j
      var new_seq = swap_seq(seq, i,i+1,j,j+1);

      var v = evaluate(new_seq);

      if(v < bestv) {bestv = v, seq = new_seq; };

    }

  }

  return seq;

}

function preciseMutate1(orseq) {  

  var seq = orseq.clone();

  var bestv = evaluate(seq);
  for(var i=0; i
    var new_seq = seq.clone();

    new_seq.swap(i, i+1);

    var v = evaluate(new_seq);

    if(v < bestv) {bestv = v, seq = new_seq; };

  }

  return seq;

}

function swap_seq(seq, p0, p1, q0, q1) {

  var seq1 = seq.slice(0, p0);

  var seq2 = seq.slice(p1+1, q1);

  seq2.push(seq[p0]);

  seq2.push(seq[p1]);

  var seq3 = seq.slice(q1, seq.length);

  return seq1.concat(seq2).concat(seq3);

}

function doMutate(seq) {

  mutationTimes++;
  do {

    m = randomNumber(seq.length - 2);

    n = randomNumber(seq.length);

  } while (m>=n)
    for(var i=0, j=(n-m+1)>>1; i
      seq.swap(m+i, n-i);

    }

    return seq;

}

function pushMutate(seq) {

  mutationTimes++;

  var m,n;

  do {

    m = randomNumber(seq.length>>1);

    n = randomNumber(seq.length);

  } while (m>=n)
  var s1 = seq.slice(0,m);

  var s2 = seq.slice(m,n)

  var s3 = seq.slice(n,seq.length);

  return s2.concat(s1).concat(s3).clone();

}

function setBestValue() {

  for(var i=0; i

    values[i] = evaluate(population[i]);

  }

  currentBest = getCurrentBest();

  if(bestValue === undefined || bestValue > currentBest.bestValue) {

    best = population[currentBest.bestPosition].clone();

    bestValue = currentBest.bestValue;

    UNCHANGED_GENS = 0;

  } else {

    UNCHANGED_GENS += 1;

  }

}

function getCurrentBest() {

  var bestP = 0,

  currentBestValue = values[0];
  for(var i=1; i

    if(values[i] < currentBestValue) {

      currentBestValue = values[i];

      bestP = i;

    }

  }

  return {

    bestPosition : bestP

    , bestValue    : currentBestValue

  }

}

function setRoulette() {

  for(var i=0; i
  var sum = 0;

  for(var i=0; i
  for(var i=0; i
  for(var i=1; i
}

function wheelOut(rand) {

  var i;

  for(i=0; i
    if( rand <= roulette[i] ) {

      return i;

    }

  }

}

function randomIndivial(n) {

  var a = [];

  for(var i=0; i
    a.push(i);

  }

  return a.shuffle();

}

function evaluate(indivial) {

  var sum = dis[indivial[0]][indivial[indivial.length - 1]];

  for(var i=1; i
    sum += dis[indivial[i]][indivial[i-1]];

  }

  return sum;

}

function countDistances() {

  var length = points.length;

  dis = new Array(length);

  for(var i=0; i
    dis[i] = new Array(length);

    for(var j=0; j
      dis[i][j] = distance(points[i], points[j]); 

    }

  }

}

3.2.2. Лістинг головного файлу «Main.js»

var canvas, ctx;

var WIDTH, HEIGHT;

var points = [];

var running;

var canvasMinX, canvasMinY;

var doPreciseMutate;
var POPULATION_SIZE;

var ELITE_RATE;

var CROSSOVER_PROBABILITY;

var MUTATION_PROBABILITY;

var OX_CROSSOVER_RATE;

var UNCHANGED_GENS;
var mutationTimes;

var dis;

var bestValue, best;

var currentGeneration;

var currentBest;

var population;

var values;

var fitnessValues;

var roulette;
$(function() {

  init();

  initData();

  points = data200;

  $('#addRandom_btn').click(function() {

    addRandomPoints(50);

    $('#status').text("");

    running = false;

  });

  $('#start_btn').click(function() { 

    if(points.length >= 3) {

      initData();

      GAInitialize();

      running = true;

    } else {

      alert("add some more points to the map!");

    }

  });

  $('#clear_btn').click(function() {

    running === false;

    initData();

    points = new Array();

  });

  $('#stop_btn').click(function() {

    if(running === false && currentGeneration !== 0){

      if(best.length !== points.length) {

          initData();

          GAInitialize();

      }

      running = true;

    } else {

      running = false;

    }

  });

});

function init() {

  ctx = $('#canvas')[0].getContext("2d");

  WIDTH = $('#canvas').width();

  HEIGHT = $('#canvas').height();

  setInterval(draw, 10);

  init_mouse();

}

function init_mouse() {

  $("canvas").click(function(evt) {

    if(!running) {

      canvasMinX = $("#canvas").offset().left;

      canvasMinY = $("#canvas").offset().top;

      $('#status').text("");
      x = evt.pageX - canvasMinX;

      y = evt.pageY - canvasMinY;

      points.push(new Point(x, y));

    }

  });

}

function initData() {

  running = false;

  POPULATION_SIZE = 30;

  ELITE_RATE = 0.3;

  CROSSOVER_PROBABILITY = 0.9;

  MUTATION_PROBABILITY  = 0.01;

  //OX_CROSSOVER_RATE = 0.05;

  UNCHANGED_GENS = 0;

  mutationTimes = 0;

  doPreciseMutate = true;
  bestValue = undefined;

  best = [];

  currentGeneration = 0;

  currentBest;

  population = []; //new Array(POPULATION_SIZE);

  values = new Array(POPULATION_SIZE);

  fitnessValues = new Array(POPULATION_SIZE);

  roulette = new Array(POPULATION_SIZE);

}

function addRandomPoints(number) {

  running = false;

  for(var i = 0; i
    points.push(randomPoint());

  }

}

function drawCircle(point) {

  ctx.fillStyle   = '#000';

  ctx.beginPath();

  ctx.arc(point.x, point.y, 3, 0, Math.PI*2, true);

  ctx.closePath();

  ctx.fill();

}

function drawLines(array) {

  ctx.strokeStyle = '#f00';

  ctx.lineWidth = 1;

  ctx.beginPath();
  ctx.moveTo(points[array[0]].x, points[array[0]].y);

  for(var i=1; i
    ctx.lineTo( points[array[i]].x, points[array[i]].y )

  }

  ctx.lineTo(points[array[0]].x, points[array[0]].y);
  ctx.stroke();

  ctx.closePath();

}

function draw() {

  if(running) {

    GANextGeneration();

    $('#status').text("There are " + points.length + " cities in the map, "

                      +"the " + currentGeneration + "th generation with "

                      + mutationTimes + " times of mutation. best value: "

                      + (bestValue));

  } else {

    $('#status').text("There are " + points.length + " Cities in the map. ")

  }

  clearCanvas();

  if (points.length > 0) {

    for(var i=0; i

      drawCircle(points[i]);

    }

    if(best.length === points.length) {

      drawLines(best);

    }

  }

}

function clearCanvas() {

  ctx.clearRect(0, 0, WIDTH, HEIGHT);

}

Блок-схема



















Хромосоми генетичного алгоритму





Рис.1 Початкова сторінка.



Рис.2 Додання 50 рандомних точок.



Рис.3 Додання 100 рандомних точок.



Рис.4 Кінець роботи програми.

Час до мутації

Кількість точок	Час до мутації (хв)
50	15
100	30
150	45
200	60
250	75
300	90
350	105
400	120
450	135
500	150
550	180
600	200
650	250

Розділ 4. Кількісні характеристики роботи ГА у відповідності з технічними характеристиками ПК та модифікації ГА

Характеристики ПК:

Процесор: Intel® Core™ i5-6200U CPU

Кількість фізичних ядер: 2.

Кількість логічних ядер: 2.

Базова тактова частота: 2,8 ГГц

Пам’ять: 8 ГБ SSD

Тип системи: x64

Модифікація ГА:

Початкова кількість поколінь:100;

Шанс мутації: 10%;

Кількість ітерацій: 5000

Середня швидкість сходження при вказаних характеристиках ГА на вказаній машині до 15 секунд.

ВИСНОВОК

Основна ідея полягає в обчисленні та запам'ятовуванні шляху від вихідного міста і до кожного з решти міст, потім підсумовування цієї величини з шляхом з кожного з інших міст до решти міст і т. Д. Перевага даного методу D перед методом повного перебору F полягає в суттєвому скороченні повного обсягу обчислень за рахунок значного збільшення об’єма пам’яті.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. 
   Орлов А.Н., Курейчик В.В., Кудрякова Т.Ю. Комбинированный алгоритм решения задачи прямоугольного раскроя // Труды Конгресса по интеллектуальным системам и информационным технологиям «IS&IT’15». Научное издание в 3-х т. Т. 3. – Таганрог: Издво ЮФУ, 2015. – С. 212-217.
   
2. 
   Kuliev E.V. Dukkardt A.N, Kureychik V.V. Legebokov A.A. Neighborhood Research Approach in Swarm Intelligence for Solving the Optimization Problems // Proceedings of IEEE EastWest Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, September 26–29, 2014. – P. 112-115.
   
3. 
   Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: ФИЗМАТЛИТ, 2003. – 432 с.
   
4. 
   E. Hadjiconstantinou and N. Christofides, "Anexact algorithm for general, orthogonal, two-dimensional knapsack problems", European Journal of Operational Research 83 (1995) 39-56.
   
5. 
   R.D.Tsai, E.M. Malstrom and H.D. Meeks, "A two-dimensional palletizing procedure for warehouse loading operations", IIE Transactions 20 (1988) 418–425.
   
6. 
   А.С. Мухачева, А.В. Чиглинцев Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя, Информационные технологии. – 2001. – №3. – С. 27–31.
   
7. 
   Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. №1. – С 2–7.
   
8. 
   Баодин Л., Теория и практика неопределенного программирования. –М.: БИНОМ, Лаборатория знаний 2005, -416 c.: ил.
   
9. 
   Рутковская Д., Пилинський М., Рутковский Л., Нейронные сети, генетические алгоритмы и нечеткие системы. – М.: Горячая линия-Телеком, 2006. – 452 с.
   

скачати