Question

solve the Travelling salesman problem and timetable problem using Genetic Algorithm

Max 2 generations for each problem with population size between 3 to 5 per generation

Answer #1

```
// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
// Number of cities in TSP
#define V 5
// Names of the cities
#define GENES ABCDE
// Starting Node Value
#define START 0
// Initial population size for the algorithm
#define POP_SIZE 5
// Structure of a GNOME
// string defines the path traversed
// by the salesman while the fitness value
// of the path is stored in an integer
struct individual
{
string gnome;
int fitness;
};
// Function to return a random number
// from start and end
int rand_num(int start, int end)
{
int r = end - start;
int rnum = start + rand() % r;
return rnum;
}
// Function to check if the character
// has already occurred in the string
bool repeat(string s, char ch)
{
for (int i = 0; i < s.size(); i++)
{
if (s[i] == ch)
return true;
}
return false;
}
// Function to return a mutated GNOME
// Mutated GNOME is a string
// with a random interchange
// of two genes to create variation in species
string mutatedGene(string gnome)
{
while (true)
{
int r = rand_num(1, V);
int r1 = rand_num(1, V);
if (r1 != r)
{
char temp = gnome[r];
gnome[r] = gnome[r1];
gnome[r1] = temp;
break;
}
}
return gnome;
}
// Function to return a valid GNOME string
// required to create the population
string create_gnome()
{
string gnome = "0";
while (true)
{
if (gnome.size() == V)
{
gnome += gnome[0];
break;
}
int temp = rand_num(1, V);
if (!repeat(gnome, (char)(temp + 48)))
gnome += (char)(temp + 48);
}
return gnome;
}
// Function to return the fitness value of a gnome.
// The fitness value is the path length
// of the path represented by the GNOME.
int cal_fitness(string gnome)
{
int map[V][V] = {{0, 2, INT_MAX, 12, 5},
{2, 0, 4, 8, INT_MAX},
{INT_MAX, 4, 0, 3, 3},
{12, 8, 3, 0, 10},
{5, INT_MAX, 3, 10, 0}};
int f = 0;
for (int i = 0; i < gnome.size() - 1; i++)
{
if (map[gnome[i] - 48][gnome[i + 1] - 48] == INT_MAX)
return INT_MAX;
f += map[gnome[i] - 48][gnome[i + 1] - 48];
}
return f;
}
// Function to return the updated value
// of the cooling element.
int cooldown(int temp)
{
return (90 * temp) / 100;
}
// Comparator for GNOME struct.
bool lessthan(struct individual t1,
struct individual t2)
{
return t1.fitness < t2.fitness;
}
// Utility function for TSP problem.
void TSPUtil(int map[V][V])
{
// Generation Number
int gen = 1;
// Number of Gene Iterations
int gen_thres = 2;
vector<struct individual> population;
struct individual temp;
// Populating the GNOME pool.
for (int i = 0; i < POP_SIZE; i++)
{
temp.gnome = create_gnome();
temp.fitness = cal_fitness(temp.gnome);
population.push_back(temp);
}
cout << "\nInitial population: " << endl
<< "GNOME FITNESS VALUE\n";
for (int i = 0; i < POP_SIZE; i++)
cout << population[i].gnome << " "
<< population[i].fitness << endl;
cout << "\n";
bool found = false;
int temperature = 10000;
// Iteration to perform
// population crossing and gene mutation.
while (temperature > 1000 && gen <= gen_thres)
{
sort(population.begin(), population.end(), lessthan);
cout << "\nCurrent temp: " << temperature << "\n";
vector<struct individual> new_population;
for (int i = 0; i < POP_SIZE; i++)
{
struct individual p1 = population[i];
while (true)
{
string new_g = mutatedGene(p1.gnome);
struct individual new_gnome;
new_gnome.gnome = new_g;
new_gnome.fitness = cal_fitness(new_gnome.gnome);
if (new_gnome.fitness <= population[i].fitness)
{
new_population.push_back(new_gnome);
break;
}
else
{
// Accepting the rejected children at
// a possible probablity above threshold.
float prob = pow(2.7,
-1 * ((float)(new_gnome.fitness - population[i].fitness) / temperature));
if (prob > 0.5)
{
new_population.push_back(new_gnome);
break;
}
}
}
}
temperature = cooldown(temperature);
population = new_population;
cout << "Generation " << gen << " \n";
cout << "GNOME FITNESS VALUE\n";
for (int i = 0; i < POP_SIZE; i++)
cout << population[i].gnome << " "
<< population[i].fitness << endl;
gen++;
}
}
int main()
{
int map[V][V] = {{0, 2, INT_MAX, 12, 5},
{2, 0, 4, 8, INT_MAX},
{INT_MAX, 4, 0, 3, 3},
{12, 8, 3, 0, 10},
{5, INT_MAX, 3, 10, 0}};
TSPUtil(map);
}
```

Here's travelling salesman problem using genetic algo.

please upvote :))

compare between Genetic Algorithms ( GA) and Particle Swarm
Optimization (PSO) algorithms to solve Travelling Salesman Problem
(TSP): find shortest path to visit 26 cities. write java code for
both , then run the to compare between them in terms of time
complexcity and optimality (show the optimal path found by each
algorithm).

An exponential algorithm requires 4^n (four to the power n)
steps to solve a problem with an input of size n. Suppose
it has been found that using today's computer, a direct
implementation of that algorithm would be able to handle an input
size of 30 in 10 years. If the computer is speeded up by a factor
of 100 (with no other changes), what input size can be processed in
the same time? Explain your answer.
(Hint: speeding up...

Solve the following LP problem graphically using level
curves.
MAX: 7 X1 + 4 X2
Subject to: 2X1 + X2 ≤ 16
X1 + X2 ≤ 10
2X1 + 5 X2 ≤ 40
X1, X2 ≥ 0
a. X1 = 4
b. X1 = 6
c. X1 = 8
d. X1 = 10

Where are the local max/min for the function
9sin(5πx) between x=0 and x=2/5? Do this problem
by sketching the graph and thinking instead of using calculus.
Local maximum at x=
Local minimum at x=

Set up each problem to be solve using both disk/washer and shell
method. Identify which is easier to solve by hand and why.
1) y = x^2 , x = 1, y = 0, x = 0, about x = -1
2) y = x^2 + 1, x = y – 3, about y = -1

1. Explain how sexual recombination generates genetic
variability
2. List the five conditions of Hardy-Weinberg equilibrium
3. Apply the Hardy-Weinberg equation to a population genetics
problem
4. Explain why natural selection is the only mechanism that
consistently produces adaptive
change
5. Explain the role of population size in genetic drift
6. List four reasons why natural selection cannot produce
perfect organisms

Solve this problem using excel: Delta Airlines quotes a flight
time of 2 hours, 5 minutes for itsflights from Cincinnati to Tampa.
Suppose we believe that actual flight times are uniformly
distributed between 2 hours and 2 hours,20 minutes.
a. Show the graph of the probability density function for flight
time
b. what is the probability that the flight will be no more than
5 minutes late
c. what is the probability that the flight will be more than 10...

Solve the given initial value problem using the method of
undetermined coefficients
yII + 4yI + 4y = (3+x)e-2x y(0)
= 2, yI(0) = 5

Solve the following using java
Write a program that runs three threads, each thread randomizes a
number between 1 and 100. The main thread waits for all the others
to finish, calculates the maximum of the numbers, which were
randomized, and prints it.
Random number 1: 10
Random number 2: 38
Random number 3: 81
Max: 81
Note: You should create 3 threads in adition to the main
thread. Also, you can use a single thread class and create 3...

Write pseudo-code to solve the problem using MapReduce and
explain how it works.
Each line in the file lists a person’s ID, name, age, and the
number of friends he or she has. For example line 1 indicates that
the person has ID of 0, his name is Will, his age is 33, and he has
385 friends. Given the file, find out the average number of friends
by age.
0,Will,33,385
1,Jean-Luc,26,2
2,Hugh,55,221
3,Deanna,40,465
4,Quark,68,21
5,Weyoun,59,318

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 16 minutes ago

asked 18 minutes ago

asked 24 minutes ago

asked 33 minutes ago

asked 41 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago