TriangulumAI

Overview

This repository implements an AI-driven approach to solving the Monochromatic Triangle Problem. It leverages a genetic algorithm (GA), combined with a two-opt local search, to optimize vertex coloring in a complete graph with the goal of minimizing monochromatic triangles. A visualization module provides real-time feedback on the GA's progress, depicting the graph, vertex coloring, and the best solution found so far.

Features

• Genetic Algorithm (GA) Implementation: Employs a complete GA pipeline, including:
  • Initialization: Randomly generates a population of vertex coloring solutions based on input data.
  • Fitness Evaluation: Quantifies the quality of each solution by considering the number of monochromatic triangles and edge lengths.
  • Selection: Uses tournament selection to choose parent solutions for reproduction.
  • Crossover: Combines genetic material from parent solutions to create offspring.
  • Mutation: Introduces random variations to offspring to maintain diversity within the population.
  • Elitism: Tracks and maintains the best-performing solution across generations.
• Two-Opt Local Search: Optimizes solutions generated by the GA by iteratively swapping pairs of vertices in the solution.
• Monochromatic Triangle Detection: Implements an efficient algorithm to identify and count monochromatic triangles within the graph, used as part of the fitness evaluation.
• CSV Data Input: Reads vertex coordinates from CSV files using the pandas library, allowing for easy integration with custom datasets.
• Real-Time Visualization: Provides a visual representation of the graph and the GA's optimization process using matplotlib and tkinter. Key visual elements include:
  • Vertex representation with color-coding based on assigned colors
  • Highlighting of monochromatic triangles
  • Visualization of the best solution's path through the graph
• GUI Parameter Control: Kivy framework that enables easy parameter adjustments for the GA.

Technologies Used

• Python 3.x: Core programming language
• networkx: Used for graph representation and manipulation. Facilitates the creation of complete graphs and calculation of triangles.
• numpy: Provides numerical computation capabilities for fitness calculations and data handling.
• pandas: Provides efficient data structure called dataframes and tools for handling CSV data.
• tkinter: Enables basic GUI elements for file browsing and visualization.
• kivy: Enables GUI and parameterization.
• matplotlib: Used to render graphs and visualize.

Installation

1. Clone the repository:

   git clone [repository URL]
   cd [repository name]
   

2. Install the required packages using pip:

   pip install networkx numpy pandas matplotlib kivy
   

   • It's highly recommended to use a virtual environment (e.g., venv or conda) to isolate project dependencies and avoid conflicts with other Python packages.

Usage

1. Prepare your data:

   • Create a CSV file containing vertex coordinate data. The file must have two columns, named numberrange_x and numberrange_y, representing the x and y coordinates of each vertex.

   • Example data.csv format:

     numberrange_x,numberrange_y
     1.0,2.0
     3.0,4.0
     5.0,6.0
     ...
     

2. Run the main script:

   python main.py
   

3. Interact with the GUI:

   • Use the "Browse" button to select your data file.
   • Adjust the following GA parameters:
     • Generations: The number of iterations the GA will run for.
     • Population Size: The number of solutions in each generation.
     • Mutation Rate: The probability of a gene (vertex color) mutating in an offspring.
   • Click "Start" to initiate the algorithm and visualization.

Project Structure

├── README.md # This file ├── main.py # Main application script with Kivy GUI ├── monochromatic_triangle.py # Core logic for the GA and problem ├── visualization.py # Visualization components using matplotlib and tkinter ├── data/ # Sample datasets │ └── sample_data.csv └── ...**

Code Explanation

monochromatic_triangle.py

This module implements the core logic for solving the monochromatic triangle problem using a genetic algorithm.

MonochromaticTriangle Class

• \_\_init\_\_(self, mt_data)
  • Initializes the graph (networkx.Graph), a dictionary to store vertices (self.vertices), and variables to store the best solution, its fitness, and the history of best solutions and paths.
  • mt_data: A pandas.DataFrame containing vertex coordinates.
  • Calls self.initialize(mt_data) to initialize the graph and generate an initial population of solutions.
• initialize(self, mt_data)
  • Reads vertex coordinates from the input mt_data (a pandas.DataFrame).
  • Adds each vertex to the networkx.Graph object.
  • Generates an initial population of random coloring solutions, where each solution is a list of integers representing the colors assigned to each vertex.
• fitness(self, solution)
  • Calculates the fitness of a given vertex coloring solution. The fitness function is designed to minimize the number of monochromatic triangles and edge lengths.
  • It uses nx.algorithms.triangles to count the number of triangles formed by the given solution.
  • The total length of edges is calculated by summing the lengths of edges connecting the vertices.
  • The final fitness value is a weighted sum of the triangle count and the total edge length.
• generate_monochromatic_triangles(self)
  • Iterates over the population and identifies monochromatic triangles in each solution.
  • Returns a list of monochromatic triangles for each individual in the population.
• run_ga(self, generations=100, pop_size=40, mutation_rate=0.05)

  • Implements the genetic algorithm.

  • The GA runs for a specified number of generations.

  • The population size is maintained at a specified value.

  • Uses tournament selection to pick a sample from the population.

  • Crossover, mutation, and two-opt local search are applied to evolve the population.

    • Crossover: Randomly select genes from both parents to create offspring.

    • Mutation:

      mutated_offspring = [
          [random.randint(0, num_colors - 1) if random.random() < mutation_rate else gene for gene in individual]
          for individual in offspring
      ]
      

  • The best solution (i.e., the coloring with the lowest number of monochromatic triangles) is tracked and stored.

  • The history of best solutions and paths is also maintained for visualization purposes.

• two_opt_local_search(self, solutions)
  • Implements the two-opt local search heuristic to refine the solutions generated by the GA.
  • Iteratively swaps pairs of elements (vertex colors) in the solution to improve the fitness.

visualization.py

This module implements the visualization aspects of the Monochromatic Triangle Problem solver.

MonochromaticTriangleVisualization Class

• \_\_init\_\_(self, mt_data, mt)
  • Initializes the visualization environment, including the networkx.Graph, vertex coordinates (self.vertices), matplotlib figure and axes (self.fig, self.ax), and tkinter canvas.
  • Stores a reference to the MonochromaticTriangle object (self.mt) to access the GA's state.
• draw_vertices(self)
  • Plots the vertices on the graph using matplotlib.
  • Vertices that are part of the best solution are highlighted in red.
• update_text_labels(self)
  • Updates the text labels in the visualization to display the current best solution and best fitness value.
• draw_best_path(self)
  • Draws the best path in blue arrows between vertices, iterating over the best solution list.
• update_plot(self)
  • Clears the axes and redraws the graph with the current vertex coloring.
  • Calls draw_best_path() to draw the best path.
  • Draws a circle around the graph.
  • Updates the matplotlib canvas.
• draw_nodes_in_circle(self)
  • Calculates the center point of the graph and draws a circle around the graph.
  • It then calculates the x and y coordinates for each node on the circle using trigonometric functions.
• visualize(self)
  • Initializes a tkinter window to display the visualization.
  • Iterates through the best_solution_history and best_path_history to visualize the algorithm's progress.
  • For each iteration, it draws the monochromatic triangles, nodes, edges, and the best path.
  • Uses time.sleep(1) to add a delay between iterations for better visualization.
  • Starts the tkinter main loop.
• draw_circle(self)
  • Draws a circle around the graph.
  • Calculates the center and radius of the circle based on the vertex coordinates.
  • Adds the circle as a patch to the matplotlib axes.
  • Draws labels for each vertex around the circle.

main.py

This module contains the main GUI logic for the application, built using kivy.

MonochromaticTriangleGUI Class

• \_\_init\_\_(self, \*\*kwargs)
  • Initializes the GUI elements using the Kivy framework.
  • Creates buttons for browsing data files and running the GA.
  • Sets default values for GA parameters (generations, mutation rate, population size).
  • Creates a background color and rounded rectangle for the GUI.

Contributing

Feel free to contribute to this project by submitting pull requests, reporting issues, or suggesting improvements.

License

[Choose a license, e.g., MIT License]

Future Work

• Implement more advanced crossover and mutation operators.
• Explore different local search heuristics (e.g., simulated annealing).
• Add support for different graph types (e.g., sparse graphs).
• Develop a more interactive and customizable visualization interface.
• Add documentation
• AND MOREE

Where this can go for the toolkit being developed future work guidelines and how the yellow brick road looks for us down the line and where this hybrid GA can be applied for the tools I'm making with this:

Focusing on Quantum-Inspired Optimization & Security:

Quantum-Assisted Monochromatic Triangle Minimization:

Concept: Explore using quantum annealing or gate-based quantum algorithms (like Variational Quantum Eigensolver, VQE) to find the absolute minimum number of monochromatic triangles. Classical GAs are often stuck in local optima. The potential of Quantum algorithms for this purpose is very promising. This is hard to simulate classically, particularly with larger datasets.

Novelty: Instead of directly encoding a graph coloring problem for encryption, use quantum optimization to find the best monochromatic triangle configuration. This configuration can be used as a key, or as a seed for a classical key generation algorithm. The quantum optimization step provides a layer of added complexity that is hard for classical adversaries to replicate.

Challenges: Mapping a graph coloring problem to a quantum computer requires clever encoding. Near-term quantum devices have limited qubit counts and are noisy. Developing hybrid quantum-classical algorithms is crucial.

Monochromatic Triangle Based Quantum Key Distribution (QKD):

Concept: Use the result of the Monochromatic Triangle Problem to parameterize the encoding/decoding states in a QKD protocol.

Novelty: Existing QKD protocols typically rely on mathematical or physical properties. Injecting a computationally challenging combinatorial optimization problem provides a new dimension of security. For example, Alice and Bob could agree on a graph. The "best" coloring according to the monochromatic triangle minimization is used to determine the polarization angles of photons used for key exchange in BB84. This will force EVE to go after 2 problems instead of one to obtain secret keys.

Challenges: This adds overhead to the QKD protocol. You have to ensure the monochromatic triangle problem doesn't introduce vulnerabilities or biases that EVE can exploit. Also, the problem is NP complete.

Quantum-Resistant Graph Coloring Hash Functions:

Concept: Build cryptographic hash functions based on the difficulty of the monochromatic triangle problem.

Novelty: Instead of directly using graph coloring for encryption, create a one-way function derived from the complexity of the problem. A message is mapped to a graph. The best coloring is derived to compute a value. This value is the message’s hash. Since it is impossible to reverse engineer, a quantum resistant hashing algorithm can be made. This hash value can be integrated into Blockchain solutions.

Challenges: Proving the quantum-resistance of hash functions is notoriously difficult. Performance could be an issue.

Enhancing Classical Algorithm Security with Graph Coloring

Dynamic Graph Coloring for Moving Target Defense:

Concept: Continuously change the graph structure and coloring used for encryption.

Novelty: Implement an algorithm that dynamically modifies the graph and its "optimal" coloring based on observed network traffic or system behavior. This creates a constantly moving target for attackers. Instead of a static key, the graph itself is the key, and it's evolving.

Challenges: Ensuring that the graph transformations are secure and don't introduce weaknesses. Managing the overhead of constant graph changes.

Adaptive Monochromatic Triangle Parameterization:

Concept: Adapt the parameters of the genetic algorithm (mutation rate, crossover, population size) based on observed attack patterns.

Novelty: If an intrusion detection system spots unusual activity, it can trigger a change in the GA's parameters to make it more difficult for an attacker to predict the graph coloring. The system becomes more resilient to evolving threats.

Challenges: Creating a robust feedback loop between the intrusion detection system and the GA without introducing vulnerabilities.

Multi-Layered Encryption:

Concept: Utilize the monochromatic triangle problem to seed a classical encryption algorithm (e.g., AES).

Novelty: To enhance security, the monochromatic triangle solution can be used as the seed to multiple layers of encryption. For instance, the first layer of encryption uses the monochromatic triangle solution to encrypt the original data, and the subsequent layers use different classical encryption algorithms to encrypt the output of the previous layer.

Focusing on Algorithm Improvement and Scalability:

Hybrid Local Search Techniques:

Concept: Instead of just the 2-opt local search, explore other more advanced local search algorithms (e.g., Simulated Annealing, Tabu Search, or Variable Neighborhood Search) and integrate them with the GA to improve performance.

Novelty: The effectiveness of local search can vary depending on the problem landscape. Adaptively switching between different local search methods or combining them in a hybrid approach could lead to better results. Also, evaluate which one runs the fastest.

Challenges: Fine-tuning the parameters of these different local search algorithms and integrating them smoothly with the GA.

Adaptive Parameter Control for GA:

Concept: Implement mechanisms to dynamically adjust the GA's parameters (mutation rate, crossover probability, population size) during the search.

Novelty: Traditional GAs often use fixed parameters, but the optimal values can change as the search progresses. Use techniques like self-adaptive or adaptive parameter control to automatically adjust these values based on the population's diversity or the current search stage.

Challenges: Designing effective adaptation rules that avoid premature convergence or stagnation.

Parallelization and Distributed Computing:

Concept: Exploit parallel computing techniques to speed up the GA's execution.

Novelty: Explore different parallelization strategies:

Population-based parallelization: Distribute the population across multiple cores or machines and evaluate fitness in parallel.

Island model: Run multiple GAs on different "islands" with occasional migration of solutions between them.

Challenges: Efficiently managing communication between parallel processes and balancing the workload.

Advanced Crossover and Mutation Operators:

Concept: Develop or adapt specialized crossover and mutation operators that are tailored to the characteristics of the Monochromatic Triangle Problem.

Novelty: Explore operators that exploit the problem structure, such as:

Edge-preserving crossover: Crossover operators that tend to preserve edges between vertices with similar colors.

Directed mutation: Mutation operators that bias the search towards solutions with fewer monochromatic triangles.

Challenges: Designing these operators can be complex and may require in-depth knowledge of the problem's properties.

Focusing on Visualization and Analysis:

Interactive Visualization and Exploration:

Concept: Enhance the visualization to allow users to interact with the graph and the GA's search process.

Novelty: Implement features such as:

Real-time highlighting of monochromatic triangles.

The ability to manually change vertex colors and see the impact on fitness.

Visualization of the GA's progress over time (e.g., plots of fitness values, diversity measures).

Challenges: Developing an intuitive and responsive user interface.

Performance Benchmarking and Analysis:

Concept: Conduct extensive experiments to evaluate the performance of different GA configurations and local search algorithms.

Novelty:

Systematically compare the effectiveness of different combinations of GA parameters and local search techniques.

Analyze the GA's convergence behavior and identify potential bottlenecks.

Evaluate the GA's performance on different types of graphs and datasets.

Challenges: Designing appropriate benchmarks and performance metrics.

Focusing on Constraint Handling and Real-World Applications

Constraint Handling Techniques:

Concept: Extend the GA to handle constraints on the graph coloring problem.

Novelty: Consider constraints such as:

Limiting the number of colors that can be used.

Requiring certain vertices to have specific colors.

Imposing restrictions on the adjacency of vertices with the same color.

Challenges: Integrating constraint handling mechanisms (e.g., penalty functions, repair operators) into the GA without significantly degrading performance.

Application to Real-World Problems:

Concept: Explore potential applications of the Monochromatic Triangle Problem (or variations of it) in areas like:

Social network analysis: Identifying communities or clusters of users with similar interests.

Resource allocation: Assigning resources to tasks while minimizing conflicts.

Image segmentation: Grouping pixels with similar characteristics into distinct regions.

Novelty: Adapt the GA to handle the specific constraints and objectives of these real-world problems.

Challenges: Mapping real-world problems to the abstract graph coloring framework.

FURTHER FUTURE WORK APPLICABLILITIES FOR FUTURE TOOLS IN THIS TOOKIT:

I. Evolutionary Computing Applications in AI Development

Automated AI Model Architecture Search:

Concept: Use a modified GA (inspired by the Monochromatic Triangle code) to automatically discover optimal architectures for AI models (e.g., neural networks, transformers). Instead of vertex coloring, the GA "colors" the different layers, connections, and hyperparameters of the model. Fitness is measured by the model's performance on a validation dataset.

Novelty: Evolve the entire model structure, from layer types and connectivity to activation functions and regularization parameters. The "Monochromatic Triangle" objective can be adapted to minimize complexity (e.g., number of parameters, computational cost) while maximizing accuracy. The model with the minimum number of "monochromatic triangles" of complexity and parameters.

Challenges: Defining a suitable encoding scheme for model architectures. Evaluating the fitness of each solution is computationally expensive.

Evolving AI Training Strategies:

Concept: Use a GA to optimize the way AI models are trained.

Novelty: Evolve the training schedule (learning rate decay, batch size changes, data augmentation strategies), the optimizer (Adam, SGD, etc.) parameters, and even the loss function itself. The Monochromatic Triangle objective can be modified to minimize the number of "conflicting" training strategies while maximizing convergence speed and final accuracy.

Challenges: Ensuring that the evolved training strategies are generalizable and don't overfit to a specific dataset.

II. Neural Network Optimization

GA-Driven Neural Network Pruning:

Concept: Use a GA to prune (remove) connections or neurons in a pre-trained neural network to reduce its size and improve its efficiency.

Novelty: Existing pruning methods often rely on heuristics or gradient-based approaches. A GA can explore a broader range of pruning strategies and optimize for a specific trade-off between accuracy and model size. The Monochromatic Triangle concept can be used to reduce the number of high edge length connections while minimizing the impact on accuracy.

Challenges: Efficiently evaluating the fitness of each pruned network. Ensuring that the pruned network maintains its generalization ability.

Neural Architecture Repair Through Graph Re-Coloring:

Concept: Post training, if a neural network's internal connections are disrupted (simulating damage or adversarial attacks), use graph re-coloring (inspired by the Monochromatic Triangle Problem) to re-establish optimal connections.

Novelty: The Monochromatic Triangle objective can be modified to incentivize re-establishing the most important connections, thus "repairing" the network's function.

Challenges: Quickly identifying damaged or disrupted connections. Guaranteeing that re-coloring doesn't introduce new vulnerabilities.

III. Cybersecurity Detection

Evolving Intrusion Detection Rules:

Concept: Use a GA to automatically generate and refine intrusion detection rules based on network traffic data.

Novelty: Current intrusion detection systems often rely on manually crafted rules or signature-based approaches. A GA can adaptively generate rules that are more resistant to evasion techniques and can detect novel attacks. Modify the Monochromatic Triangle approach to minimize the number of false positives and false negatives.

Challenges: The detection of cybersecurity is an ongoing challenge that this addresses and solves.

Evolving Malware Signatures:

Concept: A genetic algorithm, inspired by the Monochromatic Triangle Problem solver, could be adapted to evolve malware signatures that are resistant to obfuscation and polymorphism.

Novelty: By mapping the malware's code or behavior to a graph, the Monochromatic Triangle algorithm could be used to find invariant features or patterns that can serve as robust signatures.

Challenges: Designing efficient graph representations of malware code. Generating signatures that are specific enough to avoid false positives.

IV. Machine Learning Tuning & Training

Hyperparameter Optimization with Adaptive Search Space:

Concept: Combine a GA with techniques that adapt the search space for hyperparameter optimization.

Novelty: The GA can be used to explore the hyperparameter space initially, and then the search space can be narrowed down adaptively based on the GA's findings. The Monochromatic Triangle objective can be modified to find a set of hyperparameters with the least "conflict" or redundancy.

Challenges: Designing effective rules for adapting the search space.

Evolving Feature Selection Strategies:

Concept: A genetic algorithm, inspired by the Monochromatic Triangle Problem, could be used to automatically select the most relevant features for a machine learning model.

Novelty: The Monochromatic Triangle objective can be modified to minimize the number of correlated or redundant features while maximizing the model's predictive power.

Challenges: Handling high-dimensional feature spaces. Ensuring that the selected features are representative of the underlying data.

V. ETC. (Other Applications)

Resource Allocation in Cloud Computing:

Concept: Apply a modified GA (based on the Monochromatic Triangle framework) to optimize the allocation of resources (CPU, memory, storage) to virtual machines in a cloud environment.

Novelty: Optimize resource allocation to minimize "monochromatic triangles" of resource contention, improve resource utilization, and minimize energy consumption.

Challenges: Scalability, and needing complex monitoring.