Defining inequality constraint A*x <= b for genetic algorithm

Dear MATLAB Community,

I am trying to constrain the design variables in a genetic algorithm (GA). My goal is to select the xxx and yyy positions of knots (see first image step 1). After selecting these points using GA, I fit a curve to create an area (see first image step 2).

However, many knot distributions lead to self-intersecting (see second image) curves, which introduce noise and reduce computational efficiency. I already implemented this into constrraint function for checking the intersection. However, since this calls the constraint function and evaluation of the constraint function takes sometime it is not efficient.

I was wondering if i can somehow consttraint the variables with the linear inequalities A*x ≤ b so that GA will exclude those candidates before calling objective/constraint functions.

Could someone provide guidance on how to better implement these constraints so that the GA avoids invalid, self-intersecting knot distributions?

Thank you for your help!

[John D'Errico]

I'm sorry, but I am absolutely confident that no linear system of inequalities exists that will insure non-intersection of a general, complexly curved path of the kind you show. We all want for things that simply don't exist or cannot happen, else I might find a brand new, candy apple red Lamborghini sitting in my garage on X-mas day.

What can you do? Well, you can probably write a more efficient test for intersection, but we don't see what you have tried. (There are good codes out there that can test for self-intersecting paths in the plane. You can find one on the File Exchange, named intersections, by Doug Schwarz, though it would require you to resample the curved path into a series of short straight line segments.)

[Matt J]

I was wondering if i can somehow consttraint the variables with the linear inequalities A*x ≤ b so that GA will exclude those candidates before calling objective/constraint functions.

I don't know why you think linear inequalities will exclude those candidates any better than nonlinear constraints. The only kinds of constraints that allow GA to exclude candidates a prioiri are the lb,ub bounds.

[Mirhan]

Dear Matt J,

Yes, you are right. My previous explanation was misleading. I wanted to say if there is possibbility to define linear inequalities which will result in efficient algorithm.

Best regards,

[Mirhan]

Dear John D'Errico, thanks for the explanation and suggestion. I am already using an efficient intersection check algorithm. However, when the most of the candidates are self intersecting it is hard GA to continue. Therefore, i am trying to ged rid of self-intersecting instead of penalizing them.

Answer 1

[Matt J]

You should be able to vectorize the computations in your self-intersection checker (within your nonlinear constraint function). They are mainly cross-product calculations aren't they? Assuming you have done so, then you can run ga with the UseVectorized option setting so that it will get the computational benefits of this.

Answer 2

[Walter Roberson]

In order to have a hope of doing it through linear inequalities, you would have to first have a row that tested whether the first segment intersected the third segment, then whether the second segment intersected the fourth segment, and so on marching across the N'th segment intersecting the (N+2) segment. After that you would have to march across the N'th segment intersecting the (N+3) segment, then marching across the N'th segment intersecting the (N+4) segment, and so on, until eventually you hit the first segment intersecting the last segment.

Now, can you use a linear inequality to express N'th segment intersect (N+2) segment? No. The equations at https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment show that the calculations are non-linear. They are individually not especially complicated, but they are non-linear. x values must be multiplied by y values, which is not possible in linear inequalities.

So it cannot be done using linear inequalities.

[Mirhan]

Dear Walter Roberson, thanks a lot for your clear explanation.

Answer 3

[John D'Errico]

As I said in my comment, you cannot set up a linear system of inequalities to constrain that curved path from self intersections. (@Walter Roberson points this out too.) The higher order nature of the curves will prevent a linear system from being viable. Is there anything you can do? Perhaps.

Approximate the curve as a set of line segments, so a piecewise linear curve, connect-the-dots. Given the end points of each line segment, a test for two line segments crossing can then be written as a 2x2 linear system of parametric equations. That is, if two points determine a line segment, then the set of points on that line segment can be written as

P(t) = p1*(1-t) + p2*t

where t must lie between 0 and 1, and p1 and p2 are vectors of length 2. Now if you have a second line segment defined by different end points, this gives you a pair of linear equations in 2 unknowns, s and t. If the solution has both s, and t in the interval [0,1], then the line segments must intersect.

Do this for EVERY pair of line segments. Well, segment k in a piecewise linear curve will never intersect with segments k-1, k or k+1. It will get messy, and big. And again, you need to constrain the solutions so they don't lie in the unit square for each pair of parameters defining those lines. However, it will catch SOME of those intersection cases. The problem is, approximating a path by a piecewise linear set of segments will miss some intersections. And it will occasionally predict an intersection where none exists.

Typically, when I see such an approximation, the result is a necessary, but not sufficient kind of thing. In this case, the linear system will be neither necessary nor sufficient to avoid self-intersection. Honestly, I don't even like my own idea here, even if you could manage to make it work partially. I don't think the effort involved will be worth the gain, as you will still need to perform a better test on all such planar curves.

[Mirhan]

Dear John D'Errico, thanks a lot for your suggestion. I am working on implementing it. Best regards.