What explains the 2x average fitness results in TensorNEAT vs Python-NEAT? #11
Comments
|
Hi, Thank you for your interest in TensorNEAT. I completely understand your concerns, as the paper does not thoroughly explain why TensorNEAT achieves higher fitness compared to NEAT-Python in the experiments. Regarding the statement in the paper about "network encoding and the computation of distances between networks," this refers to a key difference between TensorNEAT and NEAT-Python. In TensorNEAT, input nodes are explicitly stored in the In addition to this, TensorNEAT introduces other differences compared to NEAT-Python. For instance, in NEAT-Python, the actual population size may fluctuate around the configured population size during evolution. However, in TensorNEAT, the population size is strictly fixed to ensure consistent tensor shapes during execution. Activation functions also differ between the two frameworks (TensorNEAT implementation, NEAT-Python implementation). Moreover, as mentioned in a related issue, the two frameworks also differ in the number of species generated during evolution. With these differences in mind, fitness disparities between the two frameworks are inevitable, even when the hyperparameter settings are the same (or nearly the same). It’s worth noting that the TensorNEAT paper focuses on the tensorization method for NEAT, not on optimizing fitness scores. Thus, in our experiments, we prioritized comparing the speed of the two frameworks. The hyperparameters used for NEAT-Python were not specifically tuned for higher fitness (we used the default config). Therefore, I believe that NEAT-Python could achieve better fitness results with properly tuned hyperparameters. The main purpose of Fig. 5 (left) in the paper is to demonstrate that TensorNEAT is a valid implementation of the NEAT algorithm, not to claim that it outperforms NEAT-Python in terms of fitness. Our experiments were primarily designed to evaluate the computational speed improvements brought by tensorization, not to directly compare fitness optimization capabilities between the two frameworks. The explanation in the paper could have been more detailed in addressing the fitness differences. We appreciate you bringing this to our attention! If you have further questions, feel free to ask here. |
|
Thank you for taking the time to write a thorough response. While I understand the focus of the paper on the speed, the difference in fitness was too large to be explained by the difference in hyperparameter tuning, and also consistently appeared on the around the 40th generation. Additionally, python-NEAT fully plateues which is also hard to explain with the variance in hyperparameters. But I understand that it could be out of scope for the paper to explain these differences. One additional point - a bit more significant in its implications - is that you appear to use a per-genome historical markings. In both the NEAT and hyperNEAT paper, it is a critical attribute of the historical markers that they are uniqe across the whole population. In the NEAT paper, section 3.2 it is explained that the historical markers track structural mutations globally. Also in the HyperNEAT paper they are stated as being unique. The reason for this is that strong guarantees are needed when two genomes have the same historical marker: it should unambiguously mean it is the same structural mutation in the population. Relying only on (start, end) tuple as a replacement for historical markers compromises the algorithm - this is the reason why NEAT introduced that marker in the first place as with only (start, end) keying you get a classical example of competing conventions. See figure 2 and figure 3 in the original NEAT paper. Why introduce innovation number if one could have keyed on the (in, out) tuples already? The innovation number was introduced precisely to avoid doing that. This attribute of the historical marker fundamentally limits the ability to parallelize mutation, as you do in a vmap. This means that when you speciate, different structural mutations are considered to be the same because they have the same historical marker. This has implications for crossover, mutation, and speciation. I suspect |
|
Thank you for your observations and for raising these important points. On the fitness gapThe difference in fitness between the frameworks can indeed be attributed to hyperparameter settings. Hyperparameters play a critical role in the performance of evolutionary algorithms, and suboptimal settings can often lead to premature convergence. In our experiments, NEAT-Python was run with its default configuration, which is not tuned for our specific task. For instance, parameters like species distance thresholds, mutation rates may not have been optimal for maintaining diversity and avoiding early convergence. This might explain the fitness plateau you observed around the 40th generation. On the Historical Markers (Innovation Numbers)You are absolutely correct that historical markers are a major innovation in the NEAT algorithm, as they are critical for maintaining the integrity of crossover and speciation. However, I want to clarify that both NEAT-Python and TensorNEAT do implement the concept of historical markers, though in a way that differs from the original NEAT paper. In the NEAT paper, a network is represented by a list of connections, and historical markers are assigned to each connection. In contrast, both NEAT-Python and TensorNEAT represent a network using two separate lists: one for nodes and another for connections. In these implementations, historical markers are placed on nodes rather than connections. Specifically, whenever a mutation introduces a new node, it is assigned a unique index as its historical marker (TensorNEAT implementation, NEAT-Python implementation). I personally find NEAT-Python’s approach to be elegant. It retains the advantages of historical markers outlined in the NEAT paper (e.g., valid crossover, meaningful distance calculation for speciation) while increasing the similarity among individuals within the same generation. This higher similarity enhances the efficiency of crossover by making weight exchanges more efficient, potentially leading to faster optimization of network weights. Of course, this is just my personal perspective and has not been experimentally validated. In summary, TensorNEAT does not strictly follow the implementation of historical markers as described in the NEAT paper. Instead, it adopts NEAT-Python’s approach, where historical markers are assigned to node genes rather than connection genes. While this modification differs from the original NEAT paper, I believe it does not compromise the integrity of the NEAT algorithm. I hope this explanation addresses your concerns. Please let me know if you have further questions or insights to discuss! |
|
Thank you for your patience and your prompt response.
What happens with an add-connection structural mutation which does not add a node, but is a structural mutation which deserves its own innovation historical marker? |
|
Thank you for your thoughtful question. In TensorNEAT, during an add-connection mutation, the newly added connection is identified using the tuple (input node index, output node index) as its unique identifier. Connections with the same identifier are considered homologous (i.e., originating from the same structural mutation) during crossover and speciation. This approach ensures that the structural relationships between nodes remain traceable, and connections that share the same identifier are treated as sharing the same evolutionary origin. While this differs from the global innovation numbers assigned to connections in the original NEAT paper, it retains the key advantages of historical markers, such as enabling valid crossover and meaningful speciation. If you have further concerns about this approach or its implications, I’d be happy to discuss them in more detail! |
|
Appreciate the answer. I have made a drawing to hopefully make my point better. In the first generation, the original genome diverges into two genomes: the green one gets node 4, and blue one gets node 5. The resulting edges are annotated with 3, 4 and 5, 6 respectively. In the second generation, the green genome adds a connection from 2 to 3, which gets innovation number 7. The blue genome stays as it was, and does not undergo any structural mutation (or maybe some unrelated one). In the third generation, the green genome does not change. The blue genome gets a connection from 2 to 3 as well, but now labeled with innovation 8. When we try to then crossover the green genome with the blue genome, if we line them up the original NEAT way, gene 7 and 8 will be disjoint. If we line them up by the (start, end) of the connection, they would show up as matching. This directly compromises both crossover and speciation. Genes with historical marker 7 and 8 are clearly not homologous as far as NEAT is concerned. |
|
Yes, this is precisely where TensorNEAT differs from the original NEAT paper. In the original NEAT paper, the (2, 3) connections would be considered disjoint, whereas in TensorNEAT, the (2, 3) connections would be considered matching. This does indeed deviate from the original design of the NEAT algorithm, where “only structures created by the same mutation event are considered homologous genes.” TensorNEAT’s implementation allows genomes to independently generate the same mutation at different points in time, which is biologically reasonable. Moreover, this implementation does not affect the correct execution of subsequent NEAT operations, such as crossover and speciation. Thank you very much for pointing out something I hadn’t considered before! If you have any further questions, I’d be more than happy to answer them. |
Whether a gene is matching or disjoint has direct implications in crossover. Suppose green is the fittest one. If the genes are disjoint the offspring would clearly inherit the green (2,3) link. If the genes are matching, either green or blue will be picked. If blue is picked, this might end up with the blue (2,3) being inherited. Very often the blue (2,3) link has a very different weight from the green (2,3). The offsprings will be very different. As I'm sure you know, speciation relies on distance calculation to determine species membership. This distance calculation relies directly on whether a gene is matching (take weight difference and scale it by matching factor), or whether it's disjoint (the total count of disjoint scaled by disjoint factor). The distance calculations, and subsequently the speciation outcomes, will also be very different.
This means that you treat very distant mutations with unrelated (or very distantly related) genealogy as homologous. Subsequently this homology flows down to all offsprings and speciation events. In my opinion, this is a significant departure from NEAT. NEAT was created to find a better way than topological analysis (which is what TensorNEAT is effectively doing) to track homology, and historical markers were the key insight. |
|
I understand your concern regarding TensorNEAT's differences from the original NEAT paper, especially in how connections and historical markers are handled. Let me clarify why I believe TensorNEAT’s implementation remains consistent with NEAT’s core paradigm. The core purpose of historical markers in NEAT is to allow crossover and distance calculation between different topologies. By placing historical markers on nodes rather than connections, TensorNEAT ensures that both operations can still execute correctly. By “correct execution,” I do not mean that the process is identical to the original NEAT algorithm, but rather that these operations can proceed without errors or invalid behavior. In your example, if network A has connections encoded as (2, 3, 4, 7) and network B as (1, 5, 6, 8), the original NEAT algorithm would produce an offspring with only (2, 3, 4, 7). This kind of crossover does not generate a new individual and limits exploration. TensorNEAT, on the other hand, allows connections like (2, 3) from different mutation events to be considered homologous. I believe this is reasonable because (2, 3) has a clear physical meaning in a simple network, representing a connection from I can understand your concern about this deviation, but I do not think TensorNEAT represents a “significant departure” from the NEAT paradigm. TensorNEAT still includes:
While there are differences in implementation details, TensorNEAT remains fundamentally built on the neural evolution paradigm introduced by the original NEAT paper. Thank you again for raising this thoughtful discussion! If you have any further questions or suggestions, I’d be happy to discuss them. |
|
Thank you for the answer and the patience. If, given two genomes A and B, their homology is defined differently from NEAT, the outcome of their crossover is different in NEAT, and the outcome of their speciation is different in NEAT, what is left of NEAT in this algorithm? The fact that you can do crossover is not relevant in NEAT. The contribution in NEAT was that you do crossover by lining up historical markers, not that you can do crossover in general. I do not agree that not assigning unique ( [2,3] tuple is not unique) historical markers to add-connection structural mutations is an "implementation detail". Historical markers are strictly assigned to connections, not nodes. An add-node mutation is expressed really as two add-connection mutations from the genetic POV. And connection mutations in neat-python and tensorNEAT do not get unique markers at all. They get tuples of (start, end) which are by no means guaranteed to be unique. The tuple way of identifying connections is a case of competing conventions, and I struggle to see a NEAT algorithm which considers a competing convention as part of the solution. From the paper:
Determining homology like it is done here and in neat-python is precisely ascertaining homology through direct structural analysis, hence the competing conventions problem. |
I’d like to clarify this point. Both NEAT-Python and TensorNEAT implement the historical markers mechanism. It is precisely this implementation that allows networks with different topologies to perform crossover. Without historical markers, how would we align node lists for crossover or calculate distances? In the example you provided, (2,3) corresponds to two output nodes in the network. Since output nodes are determined during the initialization phase, they naturally share the same historical markers. For nodes generated during the algorithm’s runtime via add-mutation, each new node is assigned a unique index. Connections lacking homology in their genome are inherently difficult to match. On the differences between TensorNEAT and the original NEAT paper Thank you again for your thoughtful perspective and for your interest in TensorNEAT. I appreciate the discussion. |
|
Thanks for the reply. A few followups.
Through structural analysis which is how tensorNEAT is doing it. Forget about NEAT for a moment and imagine this: I have two arbitrary networks A and B and I do this crossover: For every edge in A, I check if an edge with the same (start, end) nodes exists in B. If so I pick either A's or B's at random, and if not I pick the one from the fittest. This is crossover definitely, but it doesn't use any genetic history. This is the 'direct structural analysis' I referred to at the end of my previous comment.
This does not hurt generalization of the issue. Imagine it's the first green network (1,2,3,4) that crosses over with less fit genomes and 2-3 copies of it are produced. In one generation the first copy gets a 2->4 connection. In a subsequent generation the second copy gets again the 2->4 connection. For neat they would be disjoint, for tensorneat they would be matching because the 2->4 connection is not unique (like the historical marker in NEAT). As a result in a population you can have hundreds of structural mutations that for NEAT are disjoint, and for tensorneat are matching. This diverges the crossover and speciation, because you would do the crossover for these hundreds of mutations in the structural way, vs genetic history way. |
Thank you for presenting such an interesting hypothesis. In the scenario you described, involving two arbitrary networks A and B, how would you determine the (start, end) tuples for the connections in these networks? In other words, how would you assign identifiers to the nodes in each network? |
|
The nodes would be the same nodes that you have in tensorNEAT, and the edges would be keyed on those (start,end). However, keep in mind that the nodes will not be unique because as I said in the second paragraph of the previous comment it is easy to see a scenario where the genome gets the same edge (k0, k1) across different copies of itself in wildly different generations. If you do a direct structural analysis these edges are the exact same edges (k0, k1), and the tuple holds no history of how they came to be. Whether it's the (k0,k1) connection added to a huge genome in generation 100, or it's the (k0,k1) connection added to a small genome in generation 3 - direct structural analysis says they're the same because the tuple holds no history (k0 and k1 stay the same here from generation 3 to 100). With proper historical markers though it's trivial to distinguish the historical lineage of a (k0,k1) added at generation 100 vs a (k0, k1) added at generation 3. |
|
Let me try to explain my point in a different way. Starting with my 1, 2, 3 example suppose that the first green genome appears and gets node 4. Imagine this node 4 survives for 100 generations. Then this green genome branches into green' and green'' with node 4 still surviving in both branches. In generation 250 green' gets the 2->4 connection. After 300 more connections green'' gets 2->4 connection. Structural analysis considers these two connections as matching and homologous, which is not biologically plausible, as these genomes branched hundreds of generations ago. An even more grotesque example: if a man today has a structural mutation which links both ears together, and the next day a cat gets the same structural mutation as well joining both ears this does not make the two genes homologous. Structurally they might be similar, but this doesn't mean that the genes responsible for them are matching genes and crossover would be successful. Apologies for the ridiculous example but I'm trying to put across the point that structural analysis is very different from NEAT historical markers. It is by design that NEAT puts different historical markers on identical structural mutations. |
|
Thank you for your detailed explanation. I now fully understand your point, and this discussion has deepened my understanding of the NEAT algorithm. I truly appreciate the insights you’ve shared. Let me offer a new perspective to explain the rationale behind the implementations in TensorNEAT and NEAT-Python: Imagine every network as a complete directed graph, where for a network with From this perspective, only add-node mutations and delete-node mutations constitute actual structural changes, while all add-connection and delete-connection mutations are simply changes in weight values. For example, adding a connection is equivalent to changing the weight of a connection from zero to non-zero, and deleting a connection is the reverse. If we adopt this perspective, the implementations in TensorNEAT and NEAT-Python can be seen as perfectly aligned with the core principles of the NEAT algorithm. In summary, I fully acknowledge that TensorNEAT and NEAT-Python differ from the original NEAT algorithm in some implementation details. However, I believe these differences do not undermine the validity of the algorithm. The fundamental distinction lies in how we view the network’s structure: the NEAT paper treats connections as the basic structural units, while TensorNEAT and NEAT-Python consider nodes as the primary units. Both perspectives are valid in their own ways, and while the NEAT paper’s view is certainly correct, the alternative interpretation also holds merit—after all, whether a connection exists or has a weight of non-zero is computationally equivalent. Once again, I sincerely thank you for raising this issue. The discussions over the past few days have been incredibly rewarding for me. If you have further questions about TensorNEAT, please share them here. |
|
I'm glad you're finding this discussion helpful, and I appreciate your responsiveness. I'd like to again disagree with the view that this is an implementation detail difference and I regret I'm not able to put the key point across. I'll try to use your formulation of the problem as an adjacency matrix to make my point clearer. Suppose you have two genomes Consider: The time comes to crossover these genomes. The offspring will be genome In tensorNEAT and neat-python the reasoning is: both genomes have the In NEAT, it checks the innovation number, decides that they're clearly disjoint and picks the fittest parent. Thus it picks So in tensorNEAT and neat-python we have A similar reasoning can be applied to distance calculations and how it affects speciation. There are a few other issues with this fully connected 0-weight formulation.
|
|
Thank you for continuing this discussion and for your thoughtful points. Your example effectively highlights the differences between TensorNEAT (and NEAT-Python) and the NEAT implementation described in the original paper. I fully acknowledge these differences. However, I don’t believe that deviations from the original NEAT paper necessarily invalidate the rationality of the TensorNEAT and NEAT-Python implementations. On the fundamental difference between nodes and connectionsIn my understanding, nodes and connections are fundamentally different in a network. In NEAT, the computation process of any network (cyclic or acyclic) can be represented as follows: def network_forward(nodes, conns, input_idx, output_idx, input_values):
v_n = [NaN] * len(nodes) # initialize node values
while True:
v_n[input_idx] = input_values
v_n_new = calculate(nodes, conns, v_n) # Perform one round of computation
if v_n_new == v_n: # Node values do not change
break
v_n = v_n_new
return v_n[output_idx] Here, the computation process revolves around calculating node values, while connections serve the role of transferring these values to calculate updated ones. For nodes, structural mutation and weight mutation are fundamentally different: any addition or deletion of a node results in significant topological changes in the network (in simple terms, the shape of For connections, however, the boundary between structural mutation and weight mutation is less distinct. For example, a delete-connection mutation can be achieved simply by setting the weight of the connection to a special value:
Addressing your exampleLet’s slightly modify your example. Assume that Now, let’s say a weight mutation occurs in one genome: What I am trying to emphasize is this: NEAT-Python and TensorNEAT treat connection structural mutations as a special case of weight mutations. If you adopt this perspective, there is essentially no fundamental difference between NEAT-Python/TensorNEAT and the NEAT implementation described in the original paper. On your additional concerns
In TensorNEAT and NEAT-Python, a genome is divided into node genes and connection genes. Even if a genome is considered fully connected, the node genes still have unique historical markers. These nodes can still be treated as disjoint when performing crossover.
As I mentioned earlier, 0 is a special value for the Sum aggregation function. If the aggregation function changes, the corresponding special value can also change (e.g., 1 for Product, -inf/inf for Max/Min). For each connection, there will always be a corresponding special value to make the delete-connection mutation equivalent, as connections only interact with a specific aggregation function. |
|
After reflecting on our discussion, I believe we may have focused too much on implementation details and overlooked the broader perspective. The NEAT algorithm introduced historical markers to enable crossover and distance calculations between networks with different topologies. However, NEAT is more than just an algorithm; it represents a fundamental idea: placing evolutionary markers on the optimization target. The core of our disagreement lies in the difference in optimization targets:
NEAT-Python and TensorNEAT do implement historical markers, but they assign them to nodes instead of connections. Given the optimization target—nodes—these implementations still achieve NEAT’s core functionality: historical markers, crossover aligned by historical markers, and distance calculations using historical markers. Previously, I described the difference as an "implementation detail," but I now realize this was inaccurate. The difference is not in the implementation but in the optimization targets. NEAT-Python and TensorNEAT correctly implement NEAT’s principles while applying them to a different target. What do you think of this explanation? I’d be very interested to hear your thoughts. |
The fundamental idea is to place evolutionary markers on the gene. Why gene? Because that's what gets inherited, and that's what is used for genetic similarity. 
This binds you to have a historical marker on every gene and that is not negotiable. If it is a gene, it needs a historical marker. If it does not have a historical marker then it is not a gene and you can not inherit it. Furthermore a gene must get a globally unique marker when it appears. But you do of course inherit connections, otherwise a genome with only nodes is completely useless when you convert it to a phenotype. What you're doing is repurposing the historical markers of node genes, to stand in as historical markers for connection genes. So your historical marker for a connection gene is It is impossible to only have markers on nodes, because that would preclude connections from being inherited. If something is not a gene, it can't be inherited. And if it is a gene, it must get a globally unique number whenever it appears. |
|
Very well. I believe we need to reach an understanding on certain matters: Do you think an algorithm can only be applied to the scenarios for which it was originally proposed? In other words, can the NEAT algorithm be used to optimize other things, rather than being limited to the connection list genotype mentioned in the original paper? |
|
The NEAT algorithm - in my opinion - can be used to optimize anything really. The only restrictions I would put for the algorithm to be called NEAT are these:
Do you agree with these restrictions? What you encode in these genes (the phenotype) , can be anything: node, structures, weights, connections - whatever. |
|
I am pleased that we have reached a partial consensus. I agree with part of what you said. According to your reasoning, “ something is inherited it must be a gene.”, and each gene should have its own historical marker. However, suppose a node has three attributes (bias, aggregation_function, activation_function), and these three attributes are inherited. Each of these three attributes should have its own historical marker. But obviously, this should not be the case. Therefore, I believe that not everything involved in genetic operations should have its own historical marker. |
|
A gene can be any aggregation of things you like and inherited as a unit. Much like in NEAT a gene expresses (start, end, weight), a node can be (bias, agg, act) whatever you like it to be. In tensorNEAT and neat-python, is a connection (start,end, weight) a gene or not? |
|
If, in our discussion, a 'gene' is something that has a historical marker, then in TensorNEAT and NEAT-Python, the aggregation of all connections—which I refer to as the connection set—is a gene. The historical marker for each network's connection set is 0 (since this is present at network initialization). All mutations that occur within connections (whether structural or weight-related) are changes that happen within this gene. |
|
I don't mean the aggregation of all connections. I mean an individual connection between node A and node B for any connected A and B. Is this connection and its weight in the phenotype represented by a gene in a genotype? |
|
In our discussion, an individual connection and its weights do not constitute a gene because it does not have its own historical marker. An individual connection can be considered an attribute of the connection set, just as bias is an attribute of the node gene. |
|
I'm not sure I understand this connection set concept. Let me rephrase the question: in tensorNEAT's implementation, given a connection C in a network's phenotype, is there a gene in its genotype that is responsible for materializing it? |
|
Let me re-explain the previous few replies: In your understanding, everything that is inherited in the NEAT algorithm should be regarded as a gene, or part of a gene (just like bias is part of a gene), and every gene in the algorithm should have its own historical marker. Then, I can explain TensorNEAT and NEAT-Python as follows:
In TensorNEAT and NEAT-Python, there are only two types of structural mutations that can occur: mutate add node and mutate delete node. All other mutations can be considered as weight mutations within the gene's internal attributes. Now, back to your latest question:
My answer is no. There is no gene that directly corresponds to the connection phenotype. What corresponds to this connection phenotype is an attribute of the connection set gene. |
|
When you crossover genome A and genome B, how do you do decide which connection set gene to inherit? And if somehow A inherits B's connection set, does it mean it gets the full connection set from B? Remember that the inheritance unit is a gene, not an attribute. |
|
As I mentioned earlier, each genome has a connection set gene, and these connection set genes all have the same historical markers (because these connection set genes are created during the initialization of all networks). Therefore, during crossover, the two connection set genes are treated as homologous genes, and crossover occurs internally within their attributes, rather than Genome A getting the full connection set from Genome B. |
|
I suddenly realized that there are other discrepancies in our understanding of the NEAT algorithm, specifically regarding the crossover of homologous genes. In the original NEAT paper, the description of homologous gene crossover is 'Matching genes are inherited randomly,' whereas in the implementations of NEAT-Python and TensorNEAT, the attributes within homologous genes are exchanged. In the original NEAT paper, connection genes have only one attribute, the weight, so there is no difference between the two methods. However, in NEAT-Python and TensorNEAT , due to the consideration of more complex networks, genes can have multiple attributes. As a result, the two methods exhibit different behaviors. I believe this is a scenario that was not addressed in the NEAT paper. Therefore, the modifications to the crossover method for homologous genes in NEAT-Python and TensorNEAT are justified. |
|
This is a significant departure, because you're changing the inheritance unit here, and doing crossover not of genes, but of attributes. This is equivalent of NEAT picking apart a connection and doing crossover of starts, ends, weights and innovations separately. What happens with speciation in this scenario? Distance calculation is severely compromised because it is supposed to account for a gene for every connection. The connections are all represented by a single matching gene, thus wiping out the effect of different weights in calculating distance. No disjoint genes, no excess genes, only one matching gene. |
I'm afraid that this is not true. Connection genes hold the disabled flag too, and the paper clearly shows that. Picking weight from one gene and the enabled gene from another can be devastating as it turns off a different weight. Either this gene is off, or it is on with a given weight. It can not be on but with the other weight. |
|
Hi everyone, this is Ken Stanley, the original co-author of NEAT. sopotc sent Risto Miikkulainen and myself an email and asked us to weigh in on this discussion. I read through the discussion here and I understand the issue being discussed. As WLS2002, acknowledges, there is clearly a difference between my original implementation and TensorNEAT or PythonNEAT, namely in the choice in the latter only to keep historical markings on nodes. There are two questions this difference raises: does it adversely impact performance, and does it imply a deeper philosophical departure from the original idea? Much of the discussion in this thread seems to me more philosophical in nature, about what things mean and what the original intent was, but from a purely technical perspective focusing on performance, it is possible there is some adverse effect in terms of loss of efficiency of the overall algorithm, but that would need to be confirmed empirically. The reason it's possible for there to be an impact is that whether or not you argue that two connections with the same tuple and different weights "deserves" to be considered the same, there will be a practical implication to treating it as "the same" even in distantly related genomes. If two genomes are distant from each other, it is most likely that the two networks are simply incompatible, so viewing the genes as the same only raises the risk of wasting effort crossing over two incompatible individuals. However, it's also true that if the two genomes are truly distant genetically, then some of those differences probably will still show up in the compatibility distance calculation of speciation, and so they are likely not to be mated anyway. So if there is a problem, it probably emerges mostly in borderline cases where two genomes are right at the edge of compatibility, and would have been kept apart by original NEAT but instead are mated by TensorNEAT. Because such borderline situations are probably not that common, and also because they are borderline (i.e. they aren't actually that far apart) the overall impact might not be significant. WLS2002 also makes a case that perhaps getting more diverse recombinations could be a good thing. While that might turn out true empirically in some cases, I think ultimately it's not the most solid motivation for the choice, because if you simply want more diverse recombinations, there are more direct avenues within NEAT to achieve that, such as turning up the amount of interspecies mating or the compatibility threshold (which would cause each species to be internally more diverse). Ultimately the true impact of this choice is an empirical issue, and the best way to find out would be to run a genuine comparison. I'm not saying that is necessary to do here, but if you wanted to be really understand the practical implications, that would be the principled thing to do. Regarding the philosophical dimension, there is a lot of subtlety in the analogy with nature, but my perspective is that indeed when a gene emerges in a lineage that resembles a gene from a very distant lineage, it is not really philosophically principled to regard them as the same gene, because doing so would imply a closer relationship among the lineages that is not historically justified (as the premise is that they are very distant). For example, if a fish had a mutation that encodes the same protein as something in the human gut, I would not regard the fish as being more compatible with a human for the purposes of mating. That's why I think the connection-centered historical markings philosophically make sense. However, empirical results do not necessary correlate to philosophical elegance, so it's not clear it really matters at a practical level, but the only way to find out would be to do head-to-head comparisons in a few domains. My guess is that while there may be some difference in performance, it would likely not be very large, so it probably boils down more to an intellectual discussion than an urgent functional error. But ultimately we can't be 100% certain without empirical evidence. |
|
One other comment I'd like to add - TensorNEAT (and Python-NEAT) are wonderful contributions! I am extremely grateful to see the continued development of NEAT on more modern platforms - thanks to all the authors and programmers involved in these efforts! |
|
Hello Ken, and thanks for taking the time to weigh in. I have struggled in the last few days thinking to myself how much of a practical impact this difference would have, and swinged from little-impact to major-impact. In my head I landed on it having major impact, but your argument that speciation would keep these genomes apart anyway is a solid one that makes me swing back to the lower impact side. Also considering I'm not willing to put up the effort to perform the empirical measurement, I'm happy to accept the conclusion that the impact is likely not very large. The only actionable item from this discussion could be to note this difference in the project documentation for posterity, just in case someone wants to put in the time to measure it. Thank you @WLS2002 for your heroic patience with a random guy on the internet, and thanks again @kstanley001 for sharing your thoughts. |
|
One other point I forgot to add is that there are also implications for speciation, but like with mating I would guess they are not highly significant for performance. But it would cause species ultimately to be more inclusive than in original NEAT, for better or for worse. The practical implications of that are not so easy to disentangle. |
|
(Ok here I go again) But doesn't this more inclusive speciation undermine the argument that it is speciation that would keep the genomes apart, and thus minimize the efficiency impact? |
|
Thank you very much, @kstanley001, for sharing your thoughts on this discussion. I’d also like to thank @sopotc for raising this excellent issue. When I first started building TensorNEAT, I learned about the foundational ideas of NEAT through the original NEAT paper. However, for the implementation details of the algorithm, my primary reference was the NEAT-Python library, which was also the main baseline I compared against in the TensorNEAT paper. From my initial perspective, NEAT-Python and TensorNEAT implemented all the core aspects of the NEAT algorithm, such as historical markers, crossover, and speciation. It was only in the past few days, after sopotc pointed this out in this issue, that I realized this implementation diverges from the original paper in certain respects. Over the last few days, I revisited the NEAT paper and reflected deeply on the differences between these two approaches. My initial thought was that while there are some deviations, the impact on performance might not be significant. However, through my discussions with sopotc, I gradually came to realize that the philosophical departure of NEAT-Python and TensorNEAT from the original NEAT algorithm is more significant than I initially assumed. I agree with Stanley that the actual performance differences will ultimately need to be validated through comparative experiments. I plan to implement the original NEAT algorithm as described in the paper in TensorNEAT in the future. Specifically, this would involve using historical markers on connections as identifiers and choosing homologous genes randomly instead of exchanging attributes. Once implemented, sopotc could then run experiments to compare the practical performance impacts of these two implementations. I want to thank sopotc for raising this issue! I am also very grateful to the creator of NEAT, Ken Stanley, for paying attention to this discussion and for sharing his own perspective. This discussion has deepened my understanding of NEAT, not just on the surface level of engineering implementation but also in terms of the underlying philosophical principles. I’ve learned a great deal from this. Thank you again! |
1. Add origin_node and origin_conn. 2. Change the behavior of crossover and mutation. Now, TensorNEAT will use all fix_attrs(include historical marker if it has one) as identifier for gene in crossover and distance calculation. 3. Other slightly change. 4. Add two related examples: xor_origin and hopper_origin 5. Add related test file.
|
Hi, @sopotc, I have completed the additions to TensorNEAT based on our discussion. Now, you can use
You can run the Additionally, I’ve added two examples: I will close this issue now. If anyone still has questions, feel free to post them here. |
|
Thanks for the quick reaction on making this commit @WLS2002. I've been out-of-action with a pretty nasty flu unfortunately and haven't had a chance to take a look at this yet. I'll definitely take a look soon when I get better though. |
I'm sorry to hear that you're feeling unwell. I hope you recover quickly and feel better soon! |
Hi,
Reading the paper again I noticed that besides the faster per-generation wall time clock, you observed almost a 2x increase in fitness across 100 generations (Fig. 5).
While being on JAX it is expected the performance to be much higher, this massive difference in fitness cannot be explained by that. In the paper you state:
"This performance disparity between the two frameworks stems from the modification in the NEAT algorithm after tensorization, including network encoding and the computation of distances between networks."
How exactly could network encoding or a vmapped distance computation account for such a divergence in per-generation fitness? In principle this means that one could just change to a similar network encoding/distance computation in Python-NEAT and achieve similar fitness jump (regardless of speed).
Thanks,
Sopot
The text was updated successfully, but these errors were encountered: