1

I'm writing genetic algorithm for TPS. I've got class Chromosome that is derived from std::vector and has fitness as a member. I would like to sort population of chromosomes. IMO my operator< is 'strict weak ordering' relation. However, MVS thinks otherwise. Here is the code of operator:

bool Chromosome::operator<(const Chromosome & rhs) const
{
    const Chromosome& lhs = *this;
    if (lhs.fitness < rhs.fitness)
        return true;
    else
    {

        unsigned int size = lhs.size();
        unsigned int zeroCityIndexlhs = std::find(lhs.begin(), lhs.end(), 0) - lhs.begin();
        unsigned int zeroCityIndexrhs = std::find(rhs.begin(), rhs.end(), 0) - rhs.begin();
        for (unsigned int i = 1; i < size; i++)
        {
            if (lhs[(zeroCityIndexlhs + i) % size] < rhs[(zeroCityIndexrhs + i) % size])
                return true;
            else if (lhs[(zeroCityIndexlhs + i) % size] == rhs[(zeroCityIndexrhs + i) % size])
                continue;
            else
                return false;
        }
        return false;
    }
}

Chromosome A is less than chromosome B, when it has smaller fitness, or the same fitness and a road starting from city 0 is lexicographically lesser than road in B. Program compiles but when it comes to sorting (using std::sort()), runtime error shows up with "Debug Assertion Failed!... invalid comparator".

Improve this question
3
  • And if you took two certain chromosomes for which assert failed does operator<(a, b) == operator<(b, a)? Commented Nov 5, 2015 at 14:52
  • std::vector of what?? In other words, are you sure operator< on the contained objects is sound. Commented Nov 5, 2015 at 15:20
  • Btw you do not need else when you have return statement. Commented Nov 5, 2015 at 15:29

3 Answers 3

Reset to default
4

You're missing the other side of the fitness check:

bool Chromosome::operator<(const Chromosome & rhs) const
{
    const Chromosome& lhs = *this;
    if (lhs.fitness < rhs.fitness)
        return true;
    else if (rhs.fitness < lhs.fitness)
        return false; // <== this!

Otherwise, if lhs.fitness > rhs.fitness, you're checking the vectors, when you shouldn't.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

It works, great thanks! Seems like sometimes i have to take a break from coding
1

Use std::tuple:

bool Chromosome::operator<(const Chromosome & rhs) const
{
    // Fill in the ... here.
    using base_type = std::vector<...>;

    return std::tie(fitness, static_cast<base_type const&>(*this)) <
        std::tie(rhs.fitness, static_cast<base_type const&>(rhs));
}

Side note: inheriting from std::vector<...> is pretty horrible. Use a std::vector<...> data member and implement the functionality you need as forward functions.

Improve this answer

Comments

0

When rhs.size()<lhs.size() your comparison function looks seriously wrong. (Not just a bad comparison rule, but undefined behavior as well).

That might be fixed inside your operator[] which I don't see. So I can't be certain of the above. But since that fits the described symptoms, I am assuming you didn't actually fix it inside operator[]

Even for rhs.size()>lhs.size() there is something very questionable in your code. So it seems you are assuming they are the same size. If so, throw an assert in, so code reviewers might believe that.

Improve this answer

1 Comment

Yeah, I assumed that they are same size. I will throw assert there.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.