wierd neural network approache

Question

I'm working on a problem where I need to create a neural network to optimize the seating arrangement for 24 unique individuals in a 6x4 grid, minimizing conflicts between adjacent (up,down,left,right) persons in that grid.The goal is to design an neural network that finds the best way to seat individuals based on input conflict matrices. we have conflict matrix which is a binary matrix with shape of (24,24) that show relation between each pairs of persons where a value of 1 indicates a conflict between two individuals, and 0 indicates no conflict.Any suggestions on how to approach this problem using a neural network architecture would be greatly appreciated. Thank you!

We only have to solve this problem with supervised or unsupervised Neural network and not graph theory and optimization or graph network or Q learning or RL or other methods

my try to find solution is below:

import tensorflow as tf
import random
import numpy as np

list_of_conflicts = []

while len(list_of_conflicts) < 500:
    pairs_list = set()
    matrix = np.zeros((24, 24), dtype=int)
    
    while matrix.sum() < 40:
        num1 = np.random.choice(range(24))
        num2 = np.random.choice(range(24))
        
        if num1 == num2:
            continue
        
        pair = (num1, num2)
        if pair in pairs_list:
            continue
        
        pairs_list.add(pair)
        matrix[num1, num2] = 1

    if not any(np.array_equal(matrix, conflict) for conflict in list_of_conflicts):
        list_of_conflicts.append(matrix)

# data input is Conflict matrices
conflicts = np.array(list_of_conflicts)

def create_adjacent_mask(n_seats, seats_per_row, seats_per_col):
    adjacent_mask = np.zeros((n_seats, n_seats))
    for i in range(n_seats):
        if i % seats_per_row != 0:
            adjacent_mask[i, i-1] = 1
        if i % seats_per_row != seats_per_row-1:
            adjacent_mask[i, i+1] = 1
        if i >= seats_per_row:
            adjacent_mask[i, i-seats_per_row] = 1
        if i < n_seats-seats_per_row:
            adjacent_mask[i, i+seats_per_row] = 1
    return adjacent_mask

adjacent_mask = create_adjacent_mask(24,6,4)
# Define a function to calculate total conflicts for a given arrangement
def calculate_conflict(seating_arrangement, conflict_matrix):
    conflicts = 0
    ca_mul = tf.convert_to_tensor(conflict_matrix * adjacent_mask, tf.float64)
    conflicts = tf.reduce_sum(tf.matmul(tf.cast(seating_arrangement,tf.float64), ca_mul))
    # print(conflicts)
    return conflicts

# Custom loss function using the conflict calculation
def custom_loss(predicted_seating_arrangement, conflicts_tensor):
    loss = 0
    for i in range(predicted_seating_arrangement.shape[0]):
        conflict = tf.py_function(calculate_conflict,[predicted_seating_arrangement[i],conflicts_tensor[i]], tf.float64)
        # penalize the occurrences more than 1 
        occurrences = tf.reduce_sum(predicted_seating_arrangement[i], axis=0)

        # Calculate the number of repetitive elements
        repetitive_elements = tf.reduce_sum(tf.abs(occurrences - 1))/24

        loss += tf.cast(repetitive_elements, tf.float64) + conflict
    return tf.cast(loss, tf.float64) / tf.cast(predicted_seating_arrangement.shape[0], tf.float64)

conflicts_tensor = tf.convert_to_tensor(conflicts, tf.float64)

# Define the neural network
model = tf.keras.Sequential([
    tf.keras.layers.Input(conflicts_tensor.shape[1:]),
    tf.keras.layers.Flatten(),
    tf.keras.layers.Dense(10, activation='relu'),
    tf.keras.layers.Dense(24*24, activation='softmax'),
    tf.keras.layers.Reshape((24,24))
])

# Optimizer
optimizer = tf.keras.optimizers.Adam(learning_rate=0.01)

# Training loop
for epoch in range(2):
    with tf.GradientTape() as tape:
        predicted_seating_arrangement = model(conflicts_tensor, training=True)
        # print(predicted_seating_arrangement.shape)
        # Calculate the loss
        loss = custom_loss(predicted_seating_arrangement, conflicts_tensor)
    # Calculate the gradients
    gradients = tape.gradient(loss, model.trainable_variables)
    # Update the weights
    optimizer.apply_gradients(zip(gradients, model.trainable_variables))
    # Print the loss
    print(f'Epoch: {epoch}, Loss: {loss.numpy()}')

```

Answer 1

I think you don't need to use a neural network for the seating arrangement. Seating guests is a known problem in operational research modelled as a Quadratic Multiknapsack Problem. You can find some working approaches in this paper or this one. However, if these more formal approaches don't suit you. Genetic algorithms should work pretty well for your problem. Especially, since you have very few individuals to optimize their positions.

On the other hand, if you need to use a neural network, I would decidedly start from thinking through your loss function. It should be continuous and its value should guide your model towards the final results - something like the distance between ones multiplied by the conflict value. Additionally, I'm not sure if you should take the conflict matrix as an input and output. As I understand, you should be able to seat individuals based on model output. I would try including the conflict matrix rather in the loss function or as an auxiliary input than the solo input.

Also, start with a smaller model to prototype it faster.