nonlinear constraint problem with genetic algorithm

I am trying to use Matlab's ga function to solve the following optimization problem: given an mxnum_columns matrix X, pick k columns (k < num_columns) whose optimal least-squares reconstruction Xr minimizes the Frobenius norm :

function loss = minimum_ls(x,X)
    % extract regressor matrix using integers in x as indices into X
    S = X(:,x);
    
    % Calculate associated projection matrix which is optimal in the least
    % square error sense
    Phi = S*(inv(S'*S))*S';
    
    % Calculate optimal linear reconstruction of X for given arbitrary
    % regressor matrix
    Xr = Phi*X;
    
    % Get loss associated with this lead selection
    loss = norm(X - Xr,'fro');
end

I use the function minimum_ls as the objective function

num_columns = size(X,2)
for k = 1:num_columns
    % set options 
    options = optimoptions('ga','CrossoverFrac',0.8,...
        'UseParallel',true,...
        'UseVectorized',false);
    
    nvars = k;
    lb = ones(l,k); ub = num_columns*ones(l,k);
    IntCon = 1:k;
    nonlcon = @unique_columns;
    [~,loss(k)] = ga(@(x)minimum_ls(x,X),...
        nvars,[],[],[],[],lb,ub,nonlcon,IntCon,options);  
end

Where nonlcon requires that the integers in the variable x are unique,:

function [c,ceq] = unique_columns(x)
    c = ~(length(x) == length(unique(x))); 
    ceq = [];
end

The problem arises as k, the number of columns being selected grows bigger. As an example, X is a 306x193 matrix, and the nonlinear constraint is often not satisfied for k > 30, when I start to receive the following message:

Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance

but constraints are not satisfied.

What's going on here? For k < 30, the constraint is always satisfied, and it can be satisfied easily with the following lines of code:

x = randi(num_columns,k,1)
while (length(x) ~= length(unique(x)))
    x = randi(num_columns,k,1)
end

The above loop can take a long time for large numbers of k, but eventually it will find a solution. Is there a way to force Matlab to take more time to meet the constraint? Is there a better way to meet the constraint?