As Wikipedia points out, Nurikabe is NP-complete: it's a difficult problem. As such it's fair to use whatever you can to help a GA solve it. When we did the 3x3 magic square, it would have been cheating to tell it anything specific about the solution--because we know the solution. But if you don't know the solution, anything goes. Use the structure of the problem to help the GA. (GA's, after all, are intended for problems that don't lend themselves to more direct approaches. So the more you can do that will help the GA solve the problem the more successful you are.) So here are some thoughts about how one might approach Nurikabe.

o Determine the number of cells in the "ocean" or "stream," i.e., the non-island cells. Make that the size of the individuals. An individual is not all the cells in the grid, just the ocean cells--and we know from the start how many of them there are!

o Ensure that each individual consists of connected non-island cells with no 2x2 blocks. (See below for how you might do this. We did this for problems that required all-different.) In other words, ensure that each individual is a valid ocean.

o Let your fitness function measure how closely the islands implicitly created by an individual's ocean match the required islands. 

How to create a valid ocean

Make your individuals a sequence of cells identified by their (x,y) coordinates. That is, in a 5 x 6 Nurikabe with an ocean of 20 cells, your individuals will be a sequence of 20 (not 30) cells. Each individual is a unique (x, y) tuple (i.e., all different), where x and y are within the required ranges. (MiniZinc would have a difficult time doing this. It would take a bit of work to have a MiniZinc data structure in which each element is the name of a cell in some other array. It's not impossible, but it would take work.)

Ensure that in each individual (a) all cells are connected orthogonally; the cells do not contain a 2x2 block; the cells do not include any of the numbered cells. 

You can build such an individual by picking a non-numbered cell at random and then adding additional cells to it as long as they don't violate the constraints. 

Cross-over is like crossover for truculent or magic square: Select one parent and begin the child with an initial sequence from that parent. (You might do the rotation trick to select a place to start.) Complete the child with cells from the other parent and (as will probably be necessary) cells from neither parent that maintain the consistency of the child as a valid ocean.

Mutation takes an individual and substitutes a non-ocean cell (that doesn't violate any constraints) for a randomly selected ocean cell.

I'd suggest a larger rather than a smaller population, i.e., a population of at least 100 and perhaps larger. 

If anyone tries this, let me know how it goes and if you run into any problems.