У меня проблема с этим кодом. Это генетический алгоритм, который я пишу для задачи коммивояжера. Однако программа просто аварийно завершает работу и не завершается, копаясь в отладчике, я нашел то, что, по моему мнению, является ошибкой, однако я не уверен, где она происходит. Я просто опубликую всю программу, так как я пролил код, и я не могу точно определить ошибку. Благодарю.
#include<vector>
#include<algorithm>
#include<time.h>
#include<cmath>
#include<string>
#include<iterator>
const int numcities = 15;
using namespace std;
class City{
public:
int x,y,numcity;
City();
~City();
void setxcoord(int);
void setycoord(int);
int getxcoord();
int getycoord();
void setcitynum(int);
int getcitynum();
};
City::City(){
x = -1;
y = -1;
}
City::~City(){
}
void City::setxcoord(int xcoord){
x = xcoord;
}
void City::setycoord(int ycoord){
y = ycoord;
}
int City::getxcoord(){
return x;
}
int City::getycoord(){
return y;
}
void City::setcitynum(int newcitynum){
numcity = newcitynum;
}
int City::getcitynum(){
return numcity;
}
class resultscontainer{
public:
vector<City> tour;
int i;
vector<City>::iterator it;
resultscontainer();
~resultscontainer();
City findcity(int);
void addcity(City);
int toursize();
};
resultscontainer::resultscontainer(){
i = 0;
}
resultscontainer::~resultscontainer(){};
void resultscontainer::addcity(City newcity){
it = tour.begin() + i;
tour.insert(it,newcity);
i++;
}
City resultscontainer::findcity(int index){
City temp = tour.at(index);
return temp;
}
int resultscontainer::toursize(){
return tour.capacity();
}
class newtour{
public:
vector<City> candidate;
vector<City>::iterator it;
double fitness,distance;
string citylist;
newtour();
~newtour();
void makeindividual(resultscontainer);
double getfitness();
double getdistance();
bool fulltour();
void displaytour();
void setuniquepos(int, City);
City getcityatpos(int);
bool isEmpty(int);
};
newtour::newtour(){
City initvalue;
for(int i =0; i < numcities ; i++){
it = candidate.begin() + i;
candidate.insert(it, initvalue);
}
}
newtour::~newtour(){};
void newtour::makeindividual(resultscontainer citylist){
for (int i = 0; i < numcities; i++){
it = candidate.begin() + i;
candidate.insert(it, citylist.findcity(i));
}
random_shuffle(candidate.begin(), candidate.end());
}
double newtour::getfitness(){
fitness = 1/getdistance();
return fitness;
}
double newtour::getdistance(){
for(int i = 0; i+1 < candidate.capacity(); i++){
City currentcity = candidate.at(i);
City destinationcity = candidate.at(i+1);
distance += sqrt(pow(currentcity.x - destinationcity.x, 2) + pow(currentcity.y - destinationcity.y, 2));
}
return distance;
}
bool newtour::fulltour(){
if(candidate.capacity() == numcities) return true;
else return false;
}
void newtour::displaytour(){
citylist = "Tour is: ";
for(int i = 0; i < candidate.capacity(); i++)citylist += candidate.at(i).getcitynum() + ", ";
}
void newtour::setuniquepos(int i, City newcity){
it = candidate.begin()+i;
candidate.insert(it, newcity);
}
City newtour::getcityatpos(int i){
return candidate.at(i);
}
bool newtour::isEmpty(int i){
if(candidate.at(i).getcitynum() == NULL) return true;
else return false;
}
class population{
public:
vector< newtour > totalpop;
int index,maxpop;
vector< newtour >::iterator it;
population();
~population();
void addtour(newtour);
newtour findtour(int);
newtour findfittest();
int populationsize();
};
population::population(){
index = 0;
maxpop = 10;
}
population::~population(){}
void population::addtour(newtour candidate){
it = totalpop.begin() + index;
totalpop.insert(it, candidate);
index++;
}
newtour population::findtour(int i){
return totalpop.at(i);
}
newtour population::findfittest(){
newtour fittesttour;
for(int i = 0; i+1 < totalpop.capacity(); i++){
newtour currenttour = totalpop.at(i);
newtour nexttour = totalpop.at(i+1);
if(currenttour.getfitness() <= nexttour.getfitness()) fittesttour = nexttour;
}
return fittesttour;
}
int population::populationsize(){
return totalpop.capacity();
}
Выше находится заголовочный файл, ниже — реализация.
#include"City.h"#include<vector>
#include<algorithm>
#include<time.h>
#include<cmath>
#include<string>
#include<cstdlib>
#include<iostream>
using namespace std;
const double mutationrate = .1;
const int bracketsize = 5;
newtour bracketselection(population pop){
population temppop;
for(int i = 0; i < bracketsize; i++){
int randomnum = (int) (rand() * pop.populationsize());
temppop.addtour(pop.findtour(randomnum));
}
newtour best = temppop.findfittest();
return best;
}
newtour crossover(newtour mom, newtour dad){
newtour child;
bool inside = false;
int beginning, end;
beginning = (int) (rand() * mom.distance);
end = (int) (rand() * mom.distance);
for(int i = 0; i < numcities; i++){
if(beginning < end && i < end && i >beginning)child.setuniquepos(i, mom.getcityatpos(i));
else if (beginning > end){
if (!(i>end && i < beginning)){
child.setuniquepos(i, mom.getcityatpos(i));
}
}
}
for(int j = 0; j < numcities; j++){
for(int k = 0; k <numcities; k++)if(child.getcityatpos(k).getcitynum() == dad.getcityatpos(j).getcitynum())inside = true;
if(!inside)for(int l = 0; l < numcities; l++)if(child.getcityatpos(l).getcitynum() == NULL){
child.setuniquepos(l,dad.getcityatpos(l));
break;
}
}
return child;
}
void mutation(newtour subject){
for(int i=0; i < numcities; i++){
if(rand()* 5 / rand() < mutationrate){
int j = (int)(bracketsize *8 %5 * rand());
City randcity1 = subject.getcityatpos(i);
City randcity2 = subject.getcityatpos(j);
subject.setuniquepos(j, randcity1);
subject.setuniquepos(i, randcity2);
}
}
}
population evolve(population totalpop){
population nextgen;
nextgen.addtour(totalpop.findfittest());
for(int i = 1; i < nextgen.maxpop; i++){
newtour mom,dad,child;
mom = bracketselection(totalpop);
dad = bracketselection(totalpop);
child = crossover(mom,dad);
nextgen.addtour(child);
}
for (int i =1; i < nextgen.maxpop; i++)mutation(nextgen.findtour(i));
return nextgen;
}void main(){
City city1,city2,city3,city4,city5,city6,city7,city8,city9,city10,city11,city12,city13,city14,city15;
population thepop;
resultscontainer cities;
city1.setxcoord(5);
city1.setycoord(2);
city1.setcitynum(1);
city2.setxcoord(16);
city2.setycoord(3);
city2.setcitynum(2);
city3.setxcoord(13);
city3.setycoord(5);
city3.setcitynum(3);
city4.setxcoord(15);
city4.setycoord(9);
city4.setcitynum(4);
city5.setxcoord(10);
city5.setycoord(10);
city5.setcitynum(5);
city6.setxcoord(4);
city6.setycoord(9);
city6.setcitynum(6);
city7.setxcoord(6);
city7.setycoord(12);
city7.setcitynum(7);
city8.setxcoord(12);
city8.setycoord(13);
city8.setcitynum(8);
city9.setxcoord(9);
city9.setycoord(14);
city9.setcitynum(9);
city10.setxcoord(16);
city10.setycoord(20);
city10.setcitynum(10);
city11.setxcoord(18);
city11.setycoord(18);
city11.setcitynum(11);
city12.setxcoord(2);
city12.setycoord(5);
city12.setcitynum(12);
city13.setxcoord(7);
city13.setycoord(5);
city13.setcitynum(13);
city14.setxcoord(2);
city14.setycoord(16);
city14.setcitynum(14);
city15.setxcoord(11);
city15.setycoord(18);
city15.setcitynum(15);
cities.addcity(city1);
cities.addcity(city2);
cities.addcity(city3);
cities.addcity(city4);
cities.addcity(city5);
cities.addcity(city6);
cities.addcity(city7);
cities.addcity(city8);
cities.addcity(city9);
cities.addcity(city10);
cities.addcity(city11);
cities.addcity(city12);
cities.addcity(city13);
cities.addcity(city14);
cities.addcity(city15);
thepop = evolve(thepop);
for (int i = 0; i < 50 ; i++){
thepop = evolve(thepop);
}
newtour bestroute = thepop.findfittest();
cout << "The fittest route had a fitness of: " <<bestroute.fitness<< endl;
cout << "The algorithm determined that the best route is :" << endl;
bestroute.displaytour();
cout << "With a total distance of: " << bestroute.getdistance();
}
Вы должны использовать size()
чтобы получить количество элементов в ваших контейнерах, а не capacity()
, Это верно для циклов, как я уже упоминал в комментарии выше, но также для population::populationsize()
,
Ты звонишь rand()
и умножьте это на численность населения. Я думаю, что вы ожидаете rand()
вернуть значение с плавающей запятой от 0 до 1, но на самом деле оно возвращает целое число от 0 до RAND_MAX (которое составляет не менее 32767). Вместо того, чтобы умножать его на численность населения, вы должны модулировать его на численность населения:
int randomnum = rand() % pop.populationsize();
Модуль на ноль приведет к краху вашей программы, так же как деление на ноль, поэтому вам нужно проверить это pop.populationsize()
не равен нулю до генерации случайного числа в # 2 выше.
В newtour::displaytour()
вы пытаетесь объединить строку с целым числом candidate.at(i).getcitynum()
, Это не сработает; сначала вам нужно преобразовать целое число в строку. Я бы предложил использовать ostringstream
main()
должен вернуть int
, MSVC может позволить вам использовать void main()
, но это не соответствует стандартам, и GCC отказывается принимать его.
С этими исправлениями ваша программа выдаст следующий вывод:
Самый подходящий маршрут имел пригодность: 5,50124e + 306
Алгоритм определил, что лучшим маршрутом является:
С общим расстоянием: 1.81777e-307
Это выглядит не совсем правильно для меня, но по крайней мере это компилируется.
Я полагаю, что вы используете rand () неправильно.
Например:
int randomnum = (int) (rand() * pop.populationsize());
temppop.addtour(pop.findtour(randomnum));
randomnum будет полной ерундой и, скорее всего, будет выходить за границы поп-музыки.
Я думаю, что вы хотите что-то вроде (int)(rand() % pop.populationsize())
Также изучите отладку в VS (просто посмотрите ваш стек вызовов, пошаговый код и посмотрите значения переменных)
также используйте push_back вместо insert в функциях add … ().
Большая часть вашей проблемы, по-видимому, заключается в неправильном понимании или просто в отсутствии понимания того, как работают векторы. У вас также есть склонность к опасной практике хранения векторных итераторов в качестве членов класса вместо использования локальных переменных.
Давайте кратко рассмотрим, как вы используете вектор:
#include <iostream>
#include <string>
#include <vector>
struct Address
{
int m_doorNo;
std::string m_street;
Address() : m_doorNo(-1), m_street("Limbo")
{
std::cout << "Address() default ctor called\n";
}
Address(int doorNo, const std::string& street)
: m_doorNo(doorNo), m_street(street)
{}
};
// So we can << an Address object.
static std::ostream& operator << (std::ostream& os, const Address& address)
{
os << address.m_doorNo << " " << address.m_street.c_str();
return os;
}
// Give our *usage* of a vector a friendly name.
typedef std::vector<Address> AddressBook;
int main()
{
AddressBook book;
if (book.empty())
std::cout << "book starts empty, it has size() of " << book.size() << '\n';
book.push_back(Address(70, "1st Street"));
std::cout << "First address added, book.size = " << book.size() << '\n';
book.push_back(Address(123, "Hope Avenue"));
std::cout << "Second address added, book.size = " << book.size() << '\n';
std::cout << "address[0] is: " << book[0] << '\n';
std::cout << "address.at(1) is: " << book.at(1) << '\n';
std::cout << "*address.begin() is: " << *(book.begin()) << '\n';
std::cout << "address.front() is: " << book.front() << '\n';
std::cout << "address.back() is: " << book.back() << '\n';
// couple more addresses.
book.insert(book.begin(), Address(3, "Disco Alley"));
book.insert(book.begin() + 1, Address(5, "Mortimer Lane"));
// overshoot, place an extra address at the end of the vector.
book.insert(book.end(), Address(999, "Hellfire Drive"));
// oops, lets erase that.
book.pop_back();
std::cout << "Done shuffling. Size = " << book.size() << " while capacity = " << book.capacity() << '\n';
const size_t numAddrs = book.size();
for (size_t i = 0; i < numAddrs; ++i) {
std::cout << i << ": " << book[i] << '\n';
}
// and lastly, lets use a reverse iterator.
std::cout << "backwards:" << '\n';
// instead of std::vector<Address>::iterator etc, we can say AddressBook::iterator
for (AddressBook::reverse_iterator it = book.rbegin(); it != book.rend(); ++it) {
std::cout << *it << '\n';
}
// 'reserve' adjusts the capacity, it tells the vector to go ahead and
// allocate space for N entries, but don't make them available yet.
book.reserve(999);
// 'resize' changes the size, if the new size is smaller than the capacity,
// it forces a call to reserve to allocate more memory.
// after that, it goes ahead and grows the array storage by default-
// initializing any new entries.
book.resize(9);
std::cout << "book.size = " << book.size() << " but cap = " << book.capacity() << '\n';
// at this point, it is safe to say:
book[6].m_doorNo = 555;
book[7].m_street = "Nowhere";
book[8] = Address(10101, "Binary Bend");
for (auto it = book.begin(); it != book.end(); ++it) {
std::cout << *it << '\n';
}
return 0;
}