Hey folks, i have a problem with a vector im attempting to program. There are no compile errors but during run time i get an error saying:

"Debug Assertion Failed!

Program:...filepath\GA.exe
File:...include\vector
Line: 779

Expression: vector subscript out of range"
etc...

I have tried stepping throught the program to no avail, it seems to run fine for the time im stepping through. This leads me to beleive that somewhere, something is either running out of memory or looping too far and trying to access a part of the vector that dosnt exist. Although i cant find anywhere obvious within the program.

Im not using any complicated algorithms, just basic member functions for the vector, however the vector is a vector of a custom struct, so i was wondering if that could be the cause of the problem.

Iv attached the complete file with the header to this post for further inspection, but im pretty sure it dosnt get more complicated than the snippets below.

Here is the code for the struct and the types of member functions i have called:

struct Population
{
   Population::Population(DNA* pChrome, int iFitness)
    {m_iFitness = iFitness; m_pChrome = pChrome; m_iCumulativeFitness = 0;}
   Population::~Population(){delete m_pChrome;};
   DNA* m_pChrome;
   int  m_iFitness;
   int  m_iCumulativeFitness;
};

//vector member function example calls:
vector<Population*> m_vPopulation2; //Declaration
for(unsigned int i=0; i<m_iPopDensity; i++)
{
   Population* pTemp = new Population(ConvertToBinary(m_iDensity[i]), m_iDensity[i]);
   m_vPopulation2.push_back(pTemp);
}

//Example2

inline int GetVectorInt(int index){return m_vPopulation2[index]->m_iFitness;};

//Example 3

for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
  m_vPopulation2[i]->m_iFitness = m_iDensity[i];

//Example 4

for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
  m_vParentPop2[i] = m_vPopulation2[i]->m_pChrome->Breed(m_vParentPop2[i], m_fCrossoverChance, m_fMutateChance);

[ATTACH]17818[/ATTACH]
[ATTACH]17819[/ATTACH]

Any help muchly appreciated.

Edited 3 Years Ago by Reverend Jim: Fixed formatting

Attachments
#include "GA Class.h"

GeneticAlgorithm::GeneticAlgorithm(unsigned long int iPopDensity, unsigned int iChromeLength, unsigned int iGenerations, float fCrossoverChance, float fMutateChance)
{
	m_iPopDensity = iPopDensity;
	m_iChromeLength = iChromeLength;
	m_iGenerations = iGenerations;
	m_fCrossoverChance = fCrossoverChance;
	m_fMutateChance = fMutateChance;
	m_bRun = false;
	m_iCurrentGen = 0;

	m_RanGen = new CRandomMersenne((int)time(0));
	m_iDensity = new unsigned int [m_iPopDensity];

//	if(m_bRun)
		Initialize();
}

GeneticAlgorithm::~GeneticAlgorithm()
{
	for(int i=0; i<m_vPopulation2.size(); i++)
	{
		m_vPopulation2[i]->~Population();
		delete m_vPopulation2[i];
	}
	delete []m_iDensity;
	delete m_RanGen;
}

void GeneticAlgorithm::Initialize()
{
	//Get array of Population
		//Get array of fitness
			//Convert to binary
				//Pass to DNA
		//Get array of DNA
			//passing array of bits
		//Add 2 arrays to elements in population array

	GenerateRandomPopulation();	//Gets array of initial numbers(fitness)
	for(unsigned int i=0; i<m_iPopDensity; i++)
	{
		m_iDensity[i] = CalculateFitness(m_iDensity[i]); //Density now contains fitness
		Population* pTemp = new Population(ConvertToBinary(m_iDensity[i]), m_iDensity[i]);
		m_vPopulation2.push_back(pTemp);
	}

//	for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
//		CalculateFitness(m_vPopulation2[i].iFitness);
}

void GeneticAlgorithm::GenerateRandomPopulation()
{	
	GenerateRandomNumber();

	for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
		m_vPopulation2[i]->m_iFitness = m_iDensity[i];
}

void GeneticAlgorithm::GenerateRandomNumber()
{
	int lowest = 1;
	int highest = WorkoutHighest();
	
	for(unsigned long int i=0; i < m_iPopDensity; i++)
		m_iDensity[i] = m_RanGen->IRandom(lowest, highest);
}

void GeneticAlgorithm::GenerateRandomNumber(int highest, int &iNumberStore)
{
	iNumberStore = m_RanGen->IRandom(1, highest);
}

int GeneticAlgorithm::WorkoutHighest()
{
	double iTemp;
	iTemp = static_cast<double>(m_iChromeLength);
	int Highest = (pow(2.0, iTemp) -1);
	return Highest;
}

DNA* GeneticAlgorithm::ConvertToBinary(int number)
{
	int iTemp;
	DNA* dna;
	int* iBinaryTemp = new int[m_iChromeLength];
	iTemp = number;
	for(unsigned short int i=0; i<m_iChromeLength; i++)
	{
		if(iTemp >= 1)
		{
			if(iTemp %2 > 0)
				iBinaryTemp[m_iChromeLength - 1 - i] = 0;
			else
				iBinaryTemp[m_iChromeLength - 1 - i] = 1;
			iTemp /= 2;
		}
		else
			iBinaryTemp[m_iChromeLength - 1 - i] = 0;
	}
	dna = new DNA(iBinaryTemp, m_iChromeLength);
	return dna;
}

void GeneticAlgorithm::RouletteWheelSelection()
{
	int iRandomNumber, iTotalFitness;
	CalculateTotalFitness(iTotalFitness);
	CreatePie();
	for(unsigned long int i=0; i<m_iPopDensity; i++)
	{
		GenerateRandomNumber(iTotalFitness, iRandomNumber);
		for(unsigned long int j=m_iPopDensity - 1; j >= 0; j)
		{
			if(iRandomNumber > m_vPopulation2[j]->m_iCumulativeFitness)
				j--;
			else
			{
				m_vParentPop2[i] = m_vPopulation2[j]->m_pChrome;
				break;
			}
		}
	}
}

void GeneticAlgorithm::CalculateTotalFitness(int &iTotalFitness)
{
	iTotalFitness = 0;
	for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
		iTotalFitness += m_vPopulation2[i]->m_iFitness;
}

void GeneticAlgorithm::CreatePie()
{
	for(long int i=m_vPopulation2.size()-2; i>=0; i--)
	{ 
		m_vPopulation2[i]->m_iCumulativeFitness = m_vPopulation2[i]->m_iFitness;
		m_vPopulation2[i]->m_iCumulativeFitness += m_vPopulation2[i]->m_iCumulativeFitness;
	}
}

void GeneticAlgorithm::Breed()
{
	for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
		m_vParentPop2[i] = m_vPopulation2[i]->m_pChrome->Breed(m_vParentPop2[i], m_fCrossoverChance, m_fMutateChance);
}

void GeneticAlgorithm::RunNextGeneration()
{
	if(++m_iCurrentGen <= m_iGenerations)
	{
		RouletteWheelSelection();
		Breed();
		for(unsigned long int i=0; i<m_vPopulation2.size(); i++)
		{
			m_vPopulation2[i]->m_iFitness = m_vPopulation2[i]->m_pChrome->ConvertToDecimal();
			m_vPopulation2[i]->m_iFitness = CalculateFitness(m_vPopulation2[i]->m_iFitness);
		}
	}
}
#pragma once
#include <windows.h>
#include <iostream>
#include <time.h>
#include <math.h>
#include <vector>
#include "randomc.h"
#include "DNA.h"
using namespace std;

struct Population
{
	Population::Population(DNA* pChrome, int iFitness)
	{m_iFitness = iFitness; m_pChrome = pChrome; m_iCumulativeFitness = 0;}
	Population::~Population(){delete m_pChrome;};
	DNA*	m_pChrome;
	int		m_iFitness;
	int		m_iCumulativeFitness;
};

int						CalculateFitness(int fitness);

class GeneticAlgorithm
{
private:
	//Private Varibles/Methods
	bool				m_bRun;
	vector<Population*> m_vPopulation2;
	vector<DNA*>		m_vParentPop2;
	unsigned int*		m_iDensity;
	unsigned long int	m_iPopDensity;
	unsigned int		m_iChromeLength;
	unsigned int		m_iGenerations;
	unsigned int		m_iCurrentGen;
	float				m_fCrossoverChance;
	float				m_fMutateChance;
	CRandomMersenne*	m_RanGen;
	
	int					WorkoutHighest();
	void				Initialize();
	void				GenerateRandomNumber();
	void				GenerateRandomNumber(int highest, int &iNumberStore);
//	void				ConvertToBinary();
	DNA*				ConvertToBinary(int number);
	void				CalculateTotalFitness(int &iTotalFitness);
	void				CreatePie();

public:
	//contructor/destructor
	GeneticAlgorithm(const unsigned long int iPopDensity, const unsigned int iChromeLength, 
	const unsigned int iGenerations, const float fCrossoverChance, const float fMutateChance);
	~GeneticAlgorithm();

	//methods
	void				RunNextGeneration();
	void				GenerateRandomPopulation();
	void				ReorderPopulation(bool bCumulative = false);
	void				RouletteWheelSelection();
	void				Breed();
	void				PrintPopulation();
	void				PrintPopulation(int iPosition);
	void				TestVector();
	
	//accessor methods
	inline void			SetRun(bool run){m_bRun = run;};
//	inline vector<int>	GetPopulation(){return m_vPopulation2;};
	inline int			GetCurrentGeneration(){return m_iCurrentGen;};
	inline int			GetVectorInt(int index){return m_vPopulation2[index]->m_iFitness;};
	inline int			GetVectorSize(){return m_vPopulation2.size();};
	//get chromelength
	//get generation
	//get max generation
	//get crossover rate
	//get mutate chance
	//get fitness
	//get cumulative fitness
	//get total fitness
	//get selected
	
};

/*
initialize the static variables in the constructor, will do this later for simplicity while i get the 
form of the class sorted.
*/

I'm really curious about this, but where do you initialize the size of m_vParentPop2 (your DNA vector)?

Just glancing at the code, I can only see that as the problem. I don't see anywhere where you've pushed DNA pointers into the vector before accessing its [] operator.

I'm using TextPad Search function and only see two occurrences of the use of m_vParentPop2 and each time it's used it's being accessed via [] operator... no initialization spotted.

First off there is not enough code provided to actually compile this. However, if the only error was that you are getting array overrun I am absolutely surprised.

The likely error is to do with deletion, and the use of bare-pointers in std::vectors.

E.g. Consider struct Population. Now that takes a DNA pointer and delete it. You have no copy constructor so you will have simple copy by value system, therefore you will have multiple delete of each copy of DNA* pChrome. That is particularly important for vectors since there are often extra copies and deletes in the construction and push_back as the memory is reallocated.


I am terrified of what GeneticAlgorithm does in its deletion operator, m_v_parentPop2 is not deleted but m_vPopulation2 is?

Next you are changing the size of m_vPopulatioin2 by using push_back but not adjusting the other sizes, e.g m_iDensity. BUT then you are using the size of m_vPopulation as a loop control variable -- a certain error at some point, since m_iDensity is too small.

In all, you have a big base of code that simply is buggy and interconnected to sort out. The best thing to do is to start again, and put it together bit by bit, but test each section, e.g. use vectors for all arrays, and check that the size of ALL arrays match. Check that nothing is every double deleted, nothing is not deleted. Write a register class for memory locations, or use a equivalent from a library.

Sorry to be the bearer of grim, news but integrated testing/unit testing is a valuable skill to have and practice.

Edited 6 Years Ago by StuXYZ: n/a

Comments
nice help :)
Nice catch on the pointer.

>>something is either running out of memory or looping too far and trying to access a part of the vector that dosnt exist
That's exactly what it means.

I haven't looked at the attached files yet, but I don't see anything in the code that you posted that should be cause for alarm. There could be an issue with GetVectorInt(), you may want to consider adding some validation logic to it, but I don't see a call to it so I don't know if that's actually the issue or not.

Keep running through your debug until you go through every iteration of the loop that accesses the vector. The error won't occur until (most likely) the very last iteration.

>>where do you initialize the size of m_vParentPop2 (your DNA vector)?
Pre-Determining/Initializing the size of a vector isn't necessary. It gets dynamically set as you push values into the vector.

EDIT:
@StuXYZ:
:-O Good point, I didn't realize that was a pointer.

@OP:
Yeah, if you have a pointer as a member of your class/struct, you MUST without exception write custom copy constructor, assignment operator, and destructor at minimum. If you don't, you're in for a load of headaches, as you're now seeing.

Edited 6 Years Ago by Fbody: n/a

One more issue not yet mentioned, please the comments ..

void GeneticAlgorithm::RouletteWheelSelection()
{
  int iRandomNumber, iTotalFitness;
  CalculateTotalFitness(iTotalFitness);
  CreatePie();
  for(unsigned long int i=0; i<m_iPopDensity; i++)
  {
    GenerateRandomNumber(iTotalFitness, iRandomNumber);
    for(unsigned long int j=m_iPopDensity - 1; j >= 0; j)
    {
      if(iRandomNumber > m_vPopulation2[j]->m_iCumulativeFitness)
        // Assuming j == 0 here ...
        j--;
        // ... and j being unsigned, now j == ULONG_MAX
      else
      {
        m_vParentPop2[i] = m_vPopulation2[j]->m_pChrome;
        break;
      }
    }
  }
}

This is a good candidate for getting the out_of_range exception.

>>where do you initialize the size of m_vParentPop2 (your DNA vector)?
Pre-Determining/Initializing the size of a vector isn't necessary. It gets dynamically set as you push values into the vector.

As in--

http://www.cplusplus.com/reference/stl/vector/vector/

-- nowhere in his code did I see construction of a vector with allocated space to set the size param. Nowhere for that particular vector was a push_back called.

Calling the [] operator without proper initialization can't be good.

Example--

#include <vector>

using namespace std;

int main(){
	
	vector<int> n;
	int x = n[0];
	return 0;
}

Edited 6 Years Ago by Intrade: n/a

As in--

http://www.cplusplus.com/reference/stl/vector/vector/

-- nowhere in his code did I see construction of a vector with allocated space to set the size param. Nowhere for that particular vector was a push_back called.

It's called on line 16 of the original code.

Anyway... I agree with stuXYZ's comment that there is a serious problem in the Population structure. If you have a destructor that releases a resource, you must have a copy constructor and copy-assignment operator that correctly allocate and deallocate (in the case of copy-assignment) duplicate resources; otherwise you get double destruction if you ever copy and then destroy an object of that class.

A simple test to try: Delete lint 5 of the original code, thereby getting rid of the destructor. The resulting code will surely leak memory, but at least it won't try to delete the same memory twice. Then try running it again and see how the behavior changes.

Again, deleting the destructor will not fix the problem. Instead, it will convert an acute problem into a chronic one. But it will certainly aid in the diagnosis.

It's called on line 16 of the original code.

I see I am yet again ignored. I'll leave this topic to the pros. Good day.

I see I am yet again ignored. I'll leave this topic to the pros. Good day.

You're not being ignored. You have been responded to, twice in fact, but you don't seem to understand the responses. The page you linked is a general example page for the vector constructor(s). There are actually five (5) different examples crammed into that piece of code on that page. Did you read any of the other vector pages, such as the vector::push_back() page (http://www.cplusplus.com/reference/stl/vector/push_back/)? As we are understanding you, you are talking about doing something like this:

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;

int main() {
  vector<int> myVec(10);                    //declare a 10-element vector of int

  for (int i = 0; i < myVec.size(); ++i) {  //begin vector initialization
    myVec[i] = i;
  }

  cout << "The values: " << endl;
  for (int j = 0; j < myVec.size(); ++j) {  //display the vector contents
    cout << myVec[j] << " ";
  }
  cout << endl;

  cin.get();
  return 0;
}

This is a perfectly valid and acceptable method, but is not the only way to do it, and is not always convenient because it requires that you know the size beforehand.

Observe:

#include <iostream>
#include <vector>
#include <cctype>

using std::cout;
using std::cin;
using std::endl;
using std::vector;

int main() {
  vector<int> myVec;                        //declare a 10-element vector of int
  char response = '\0';
  int someVal = 0;

  cout << "Would you like to add a value? (y/n) ";
  cin >> response;
  response = tolower(response);
  while (response == 'y') {                 //begin vector initialization
    myVec.push_back(someVal);
    ++someVal;

    //re-prompt user
    cout << "Would you like to add another value? (y/n) ";
    cin >> response;
    response = tolower(response);
  }

  cout << "Your values: " << endl;
  for (unsigned j = 0; j < myVec.size(); ++j) {  //display the vector contents
    cout << myVec[j] << " ";
  }
  cout << endl;

  cin.get();
  return 0;
}

It is legal to declare a vector of zero size. When you do, you then use std::vector::push_back() to add values to the vector, not "indexes". You do not need to know the vector's current size or capacity at all because it keeps track of it by itself. When you use push_back() it automatically updates all of that information without any help from you. If the current capacity of the vector isn't sufficient to add another element, it automatically re-allocates new storage space that is large enough to store the growing vector. This is the method used by the OP, and it is appropriate for the situation.

Edited 6 Years Ago by Fbody: n/a

As far as I can see, Intrade is right. There are two vectors involved, of which the m_vParentPop2 vector doesn't seem to be getting content in any way, whatsoever -- neither in the code snippet nor in the attached files. I.e. it's a zero-sized vector, which is illegally accessed, hence being a real concern for the OP.

Comments
Finally someone else sees it...

wow thats alot to think about. Many thanks for the replys folks, i have alot of work and research to do.

Not sure what a copy constructor is or its uses with pointers, and i need to learn more about this memory managment stuff. Ill also read more on vectors.

I had only just fiigured out that vectors arnt used the same way as arrays so you cant just loop throu sauing vector = xxx. Thats why the m_vParentPop2 was being accessed like that.

But mucho thanks folks, i shall start from scratch and make each function in an isolated enviroment for testing. @StuXYZ grim truth is always better than sugar coatedd truth :D many thanks.

>>I had only just fiigured out that vectors arnt used the same way as arrays so you cant just loop throu sauing vector = xxx. Thats why the m_vParentPop2 was being accessed like that.
They can be used in very much the same way as an array, but to do so you have to declare them properly and respect their legal boundaries, just like an array. Really, it's just a minor syntactical difference.

//declare a 10-element array of int:
int intArray[10] = {0};

//declare a 10-element vector of int:
vector<int> intVec(10, 0);

There are also other ways to work with them, as demonstrated earlier. They are very versatile, you just have to work with them the correct way for your objective(s).

Edited 6 Years Ago by Fbody: n/a

This article has been dead for over six months. Start a new discussion instead.